随着 n 变大,两个函数 log*(log n) 和 log(log* n) 会更快吗?
这里,log* 函数是迭代的对数,在这里定义:
我怀疑这些是相同的,只是写法不同,但是它们之间有什么区别吗?
随着 n 变大,两个函数 log*(log n) 和 log(log* n) 会更快吗?
这里,log* 函数是迭代的对数,在这里定义:
我怀疑这些是相同的,只是写法不同,但是它们之间有什么区别吗?
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。
另一种更直观的方式是:log* 函数在压缩大数方面比 log 函数要好得多。因此,如果你想取一个大的数字并把它变小,你可以通过首先计算 log* n 来尽可能多地收缩 n,然后使用 log 来获得更高的效率 (log (log* n))拉下剩下的东西。
希望这可以帮助!