增长速度中，log*(log *n) 和 log*(log n) 哪个更快？

Question

随着n的增大，log*(log n)和log(log* n)这两个函数中哪个会更快？

这里的log*函数是迭代对数，定义如下： log* 1(n)=log(n) log* k(n)=log*(k-1)(log(n))

我怀疑它们是相同的，只是写法不同，但它们之间有什么区别吗？

- user97452

---

如果你的星号是代表 "logstar"，也就是 n log n，你可能想要重新写一下，因为 Stack Overflow 已经按照一种你可能没有打算的方式解析了它们。 - mfsiega

好的调用，我不知道我从哪里得到了那个。 - mfsiega

如果“log*”是某个东西的简写，那么完整的定义将不胜感激。 - shuttle87

Answer 1

log* n是迭代对数，对于大的n来说被定义为

log* n = 1 + log*(log n)

因此，log*(log n)=(log* n)-1，其中log*是在值到达某个固定常数（通常为1）之前需要应用log的次数。 先进行另一个对数运算只会从过程中删除一步。

因此，log(log* n)要比log*(log n)=log* n-1小得多，因为对于任何相当大的x，log x

另一种更直观的方法是：log*函数在压缩大数字方面比log函数显着更好。 因此，如果您想要将一个大数字变小，通过先计算log* n以尽可能地压缩n，然后再使用log (log* n)来降低剩下的部分，可以获得更高的效率。

希望这可以帮助您！

- templatetypedef