计算成本

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的次数(基本上就是在n <= 2之前我们必须应用sqrt的次数)。

考虑一下这样的推理：

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