Confused о Big O нотации

Question

У меня есть два вопроса:

public static void method1(int[] a, int[] b) { 
    int sum1 = 0, sum2 = 0; 

    for(int i = 0; i < a.length; i++) { 
     sum1 += a[i]; 
    } 

    for(int i = 0; i < b.length; i++) { 
     sum2 += b[i]; 
    } 
} 

Вопрос 1: Является ли это в O (п)? Неважно, сколько циклов (не вложенных циклов) находится в method1?

Вопрос 2: Что делать, если есть

Arrays.sort(a); 

внутри method1, какую функцию она?

Answer 1

Вопрос 1: Это в O (n)?

Это правильно (здесь n обозначает длину каждого из двух массивов).

Неважно, сколько циклов (не вложенных циклов) находится в методе 1?

Это не так, если число циклов фиксировано, а число итераций в каждом цикле линейно в n. Более формально, если C - некоторая константа, C*n - O(n).

Вопрос 2: Что делать, если есть Arrays.sort(a);

Сортировка обычно O(n logn), и это то, что делает Arrays.sort(int[])в среднем. documentation расплывчат об исполнении наихудшего:

Этого алгоритм предлагает O (N журнал (п)) производительность на многих наборах данных, которые вызывают другое quicksorts деградировать квадратичную производительность, и, как правило, быстрее, чем традиционные (одна-сводная) реализация Quicksort.

Это явно обрывается гарантировать O(n logn) в худшем случае. Чтение между линиями предполагает, что это, вероятно, O(n^2).

Интересно отметить, что в JDK7 Arrays.sort(Object[]) использует другой алгоритм, который используется Arrays.sort(int[]). Первый вариант является адаптацией TimSort и поэтому должен гарантировать наихудшую производительность O(n logn). К сожалению, документация снова перестает описывать это.

Answer 2

1. a. Это O (n), где n = длина ввода (всего)
   b. Да, важно, сколько циклов существует: если это постоянное число циклов k, то это O (k * n), которое обычно рассматривается как O (n), но если k> = n, то это должно быть учтено

2. Arrays.sort(a); реализован с использованием сортировки слиянием, которая работает в O (n log n) как в среднем, так и в худшем случае (не так, как сказал NPE!).

Обновление для MrSmith42:

От http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html:
алгоритм, используемый рода (Object []) не должен быть слиянием, но он должен быть устойчивым).

А также:

банкнота Реализация: алгоритм сортировки является Dual-P ivot Quicksort Владимир Ярославский, Джон Бентли и Джошуа Блох. Этот алгоритм предлагает производительность O (n log (n)) на многих наборах данных, которые приводят к снижению производительности до быстрой квадратичной производительности и, как правило, быстрее, чем традиционные (однопоточные) реализации Quicksort.