计算成本

是否有人知道这两段代码的计算成本是多少？

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

Answer 1

第二个是O(log* n) ，其中log *是迭代对数 。

分析第一个产生这样的东西：

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