1

假设迭代对数的定义如下：http ://en.wikipedia.org/wiki/Iterated_logarithm

例如，我应该如何将其复杂性与其他功能进行比较lg(lg(n))？到目前为止，我已经通过计算限制完成了所有比较，但是如何计算迭代对数的限制？

我知道它的增长非常缓慢，比 慢lg(n)，但是是否有一些函数的增长速度可能与lg*(n)（lg*基数为 2 的迭代对数在哪里）相同，因此它可以轻松地将其与其他函数进行比较？这样我也可以比较lg*(lg(n))例如lg(lg*(n))。任何关于根据增长速度相互比较功能的技巧将不胜感激。

4

1 回答 1

0

迭代对数函数 log* n 不容易与另一个具有相似行为的函数进行比较，就像 log n 不容易与另一个具有相似行为的函数进行比较一样。

为了理解 log* 函数，我发现记住以下几点很有帮助：

  1. 这个函数增长非常缓慢。想象一下 log* 2 2 2 2 2 = 5，那个 2s 的塔是一个比已知宇宙中的原子数还大的数量。
  2. 它使用对数的方式就像对数使用除法一样。对数的商规则说 log (n / 2) = log n - log 2 = log n - 1，假设我们的日志是以 2 为底的。对此的一种直觉是，从某种意义上说，log n 表示“你必须将 n 除以多少次才能将 n 降为 1？”所以 log (n / 2) “应该”为 log n - 1因为我们事先做了一个额外的除法。另一方面，(log n) / 2 可能比 log n - 1 小很多。类似地，log* n 计数“在将 n 降到某个常数之前，您必须取 n 的对数多少次？ " 所以 log* log n = log* n - 1 因为我们已经多取了一个日志。另一方面，log log* n 可能远小于 log* n - 1。

希望这可以帮助！

于 2020-04-29T07:07:58.243 回答