Как вы находите асимптотическую временную сложность этих циклов?

Question

Как вы находите асимптотическую временную сложность этого кода?

for i=1 to n do 
    j=2 
    while j<i do 
     j=j*j 

В моих заметках у меня есть ответ O (n * log (logn)), но без объяснения.

Answer 1

Первый для цикла работает n раз. Внутренняя петля итерации в квадратах и ​​так займет O(loglogn) Итак, общая сложность O(n*log(logn)).

Чтобы понять, почему итерация на площадях принять O(log(logn)) время, увидеть этот путь:

Пусть п как большое число, как 2^16.

Initially: j = 2 
1st step : j = 2^2 
2nd step : j = 2^4 
3rd step : j = 2^8 
4th step : j = 2^16. 

Следовательно, требуется всего 4 шага, который является журналом (2^16).

Итак, теперь для любого n = 2^k вы начинаете с 2 и каждый раз, когда вы возводитесь в квадрат. Таким образом, может быть самое сложное O(logk) квадрат, который вы можете сделать, чтобы достичь k. Начиная с n = 2^k, Итак, k = log(n) и, следовательно, O(logk) такой же, как O(log(logn)).