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

Question

当n变大时,两个函数log*(log n)和log(log*n)会更快吗？

这里,log*函数是迭代对数,在此定义:

我怀疑这些是相同的,只是用不同的方式写的,但它们之间有什么区别吗？

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 <x - 1.

希望这可以帮助!