計算成本

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