Почему этот алгоритм линейный, а не линеаритический?

int sum = 0; 
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++)
      sum++;

Я был уверен, что он растет в nlogn, но ему сказали, что он линейный... Почему он линейный, а не линейный?

Ответ 1

Он линейный. Представьте себе, что второй n равен 64. Внутренний цикл работает 64 раза, затем 32 раза, затем 16 раз, затем 8 раз, затем 4 раза, затем 2 раза, затем 1 раз. 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127.

Поэтому для этого требуется 2n-1 полных операций (для мощности 2, но это не меняет анализ), предполагая, что внутренний цикл не оптимизирован. Очевидно, что O(n) - линейный.

Если внутренний цикл цикла оптимизирован (sum += n;), он логарифмичен.

Ответ 2

Сложность этого алгоритма Θ (N).

Количество операций

sum{2**k} for k = 0..log2(N)

Сумма этой прогрессии

2*N-1

который является Θ (N).

Ответ 3

Формально использование Sigma Notation может помочь вам ясно видеть, что порядок роста является линейным.