增长率log（log * n）和log *（log n）哪个更快？

Question

随着n变大，两个函数log *（log n）和log（log * n）会更快吗？

这里，log *函数是迭代对数，在这里定义：

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9IT1d0dy5wbmcifQ==” alt =“在此处输入图像描述”>

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

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小得多，因为log x

另一种更直观的方法：log *函数比log函数在压缩大数方面更好[[明显]。因此，如果您想取一个较大的数字并将其减小，则可以通过首先计算log * n来尽可能多地收缩n，然后使用log on（log（log * n））来获得更高的效率。拉下剩下的东西。

希望这会有所帮助！