Блог

Я нашел этот пример проблемы в Интернете, и я просто не могу понять, как автор пришел к их выводу.

 sum1 = 0;
for(k=1; k<=n; k*=2)    // Do log n times
   for (j=1; j<=n; j  )  // Do n times
      sum1  ;`

sum2 = 0;
for (k=1; k<=n; k*=2)    // Do log n times
   for (j=1; j<=k; j  )  // Do k times
      sum2  ;
 

Я понимаю, что время выполнения первого цикла равно O (n) = nlog (n), но автор утверждает, что для второго цикла время выполнения равно O (n) = n.

Почему это так? Самое близкое, что я могу получить к ответу, это:

 O(n) = k * log(n)
k = 2^i
O(n) = 2^i * log(n) ----> this is where I get stuck
 

Я предполагаю, что используется какое-то свойство логарифмов, но я не могу понять, какое именно. Может кто-нибудь указать мне правильное направление?
Спасибо.

Во втором примере сложность равна sum_j 2^j , т.Е. Общему количеству операций во внутреннем цикле.

Как 2^j <= n , есть logn условия.

Эта сумма равна 2^{jmax 1} - 1 , 2^jmax примерно (<=) равна n .

Тогда, по сути, сложность O (2n) = O (n).

sum2 выполняется 1 2 4 8 … K раз, где K — наибольшая степень 2, меньшая или равная n. Эта сумма равна 2K-1.

Поскольку n / 2 < K <= n (поскольку K является наибольшей степенью 2, меньшей или равной n), количество итераций составляет от n-1 до 2n-1. Это тета (n), если вы хотите выразить это в асимптотической записи.