algorithm - 哪个增长率 log(log *n) 和 log*(log n) 更快？

Question

随着 n 变大，log*(log n) 和 log(log* n) 这两个函数会更快吗？

这里，log* 函数是迭代对数，定义如下:

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

Answer 1

log* n 是 iterated logarithm ，对于大 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 < x - 1。

另一种更直观的理解方式:log* 函数在压缩大数方面比 log 函数显着更好。因此，如果您想取一个大数并使其变小，您可以通过先计算 log* n 来尽可能多地收缩 n ，然后使用 log on that (log (log* n)) 来提高效率拉下剩下的东西。

希望这对您有所帮助!