基数2上的迭代对数的复杂性

Question

假设迭代对数的定义与这里一样。http:/en.wikipedia.orgwikiIterated_logarithm。

我应该如何去比较它和其他函数的复杂度，比如说 lg(lg(n))? 到目前为止，我都是通过计算极限来进行比较的，但是如何计算迭代对数的极限呢？

我知道它的增长非常缓慢，比起 lg(n)但是否有一些函数以同样的速度增长，也许就像... ... lg*(n) (其中 lg* 是基数2上的迭代对数），这样就可以方便地与其他函数进行比较？这样我也可以比较 lg*(lg(n)) 到 lg(lg*(n)) 比如说。如果有任何根据增长速度来比较函数的技巧，我将非常感激。

Answer 1

迭代对数函数log* n不容易与另一个行为相似的函数进行比较，同样，log n也不容易与另一个行为相似的函数进行比较。

为了理解log*函数，我发现记住一些事情是有帮助的。

1. 这个函数会增长 极为 缓慢。图，对数* 2²²²² = 5, 而那座2s塔是一个比已知宇宙中原子数量更大的量。
2. 它玩的是对数，就像对数玩除法一样。对数的商规则说，对数（n 2）=对数n -对数2=对数n -1，假设我们的对数是基数2。这一点的一个直观感受是，从某种意义上说，对数n代表 "要把n除以2的次数，才能把n降到1？"所以对数（n 2）"应该 "是对数n - 1，因为我们事先多做了一次除法。另一方面，（log n）2可能比log n - 1小很多，同样，log* n算 "在把n降到某个常数之前，你要取多少次n的对数？"所以log* log n = log* n - 1，因为我们事先多取了一次对数。另一方面，log log* n可能比log* n - 1小得多。

希望这能帮到你!