Вычислительная стоимость

Question

Есть ли кто-то, кто знает, что такое вычислительная стоимость для этих двух частей кода?

while (n > 2) 
    n = sqrt(n); 

while (n > 2) 
    n = log(n); 

Answer 1

Второй будет O(log* n), где log * является iterated logarithm.

Анализируя первые один дает что-то вроде этого:

sqrt(n) = n^(1/2) 
sqrt(sqrt(n)) = n^(1/4) 
sqrt(sqrt(sqrt(n))) = n^(1/8) 
... 
sqrt applied k times = n^(1/2^k) 

Рассмотрим, что первый алгоритм выполняет k раз (в основном, сколько раз мы не применять sqrt до n <= 2).

Рассмотрим это рассуждение:

n^(1/2^k) = p (p <= 2) |^(2^k) 
n = p^(2^k) | log 
log n = (2^k) log p | log 
log log n = log (2^k) + log log p 
log log n = klog2 + log log p 
=> k ~= log log n 

Таким образом, первый алгоритм O(log log n).

Answer 2

Ответ на первый должен стать очевидным, если один переделывает его в логарифмической области:

n = log2(n); 
while (n > 1) 
    n = n/2; 

Сколько раз вам нужно сократить вдвое число для того, чтобы достичь 1? O (log n).