计算成本

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)。

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

多少次，你需要以一个减半数达到1：

Answer 2

如果重铸它在对数域中的答案，第一个应该变得明显吗？ O（log n）。