Как измерить сложность времени (Big-O) этого алгоритма?

Question

Я пытаюсь измерить сложность большой-O следующего алгоритма:

int sumSome(int[] arr){ 
    int sum = 0; 
    for (int i=0; i<arr.length; i++) { 
     for (int j=1; j<arr.length; j = j*2) { 
     if (arr[i] > arr[j]) 
      sum += arr[i]; 
     } 
    } 
    return sum; 
} 

Теперь из моего понимания,

if (arr[i] > arr[j]) 
       sum += arr[i]; 

имеет большой O в O (1), так как это постоянно и ничего происходит, однако, цикл for, который звучит, хотя я с трудом пытаюсь распознать его ноту Big-O. Я предположил, что

for (int j=1; j<arr.length; j = j*2) { 
     if (arr[i] > arr[j]) 
      sum += arr[i]; 
} 

является линейной функцией O (п), потому что J может быть 1, но это происходит в линейной форме в O (2n), который является только O (п). Таким образом, не весь алгоритм был бы O (n^2)? Видимо, я не ответил на вопрос правильно на экзамене MOOC. Благодаря!

Answer 1

Ключ к Big-O ищет петли, так что ваша ключевая часть здесь:

for (int i=0; i<arr.length; i++) { 
    for (int j=1; j<arr.length; j = j*2) { 
     if (arr[i] > arr[j]) 
     sum += arr[i]; 
    } 
} 

Внешний цикл выполняется N раз, так как он идет от 0 до N с шагом 1.

Внутренний цикл выполняет журнал N раз, на внешнюю итерацию, потому что он делает от 1 до N экспоненциально. (Я думаю, что этот фрагмент, который вы пропустили, является итератором в цикле: j = j*2.Это делает J экспоненциально, а не линейно, поэтому он достигнет N в log-base-2. Время было бы линейным, если бы оно было +2, вместо *2)

Если для Big-O не имеет значения, если он добавляет коэффициент.

Так, только умножают заказы петель: N * Log N = N Log N

Answer 2

- линейная функция O (n), поскольку j может быть 1, но она линейно возрастает при O (2n), которая является только O (n). Таким образом, весь алгоритм не был бы O (n^2). Видимо, я не ответил на вопрос правильно на экзамене MOOC. Благодаря!

Это не идет вверх по линейному закону, а в геометрической прогрессии, потому что вы умножаете j по 2 на каждой итерации.

j = 1, 2, 4, 8, 16, 32, ..., 2^k < n 
2^k < n | apply log base 2 => k < log_2 n => k = O(log n) 

Таким образом, второй цикл выполняется только O(log n) раз, что делает всю последовательность кода O(n log n).

Строго говоря, O(n^2) также является правильным ответом, потому что если O(n log n) является верхней границей, то и O(n^2). Большая тэта n^2 не была бы правильной, и люди обычно также используют Big-Oh для обозначения жестких границ.