algorithm - 迭代对数的大 theta

Question

我有两个数学函数：log(log*n) 和2^(log*n)。现在，我想计算这两个函数的渐近增长（特别是我想找到大 theta）。最后，我想比较一下它们的复杂性。谁能分享一个可以解决此类问题的正式/直观的解决方案？

谢谢。

Answer 1

这是一个有趣的。让我们从使用标准技术开始：很难推断指数，所以让我们取其对数，看看会发生什么。这给我们留下了这些功能：

日志（日志（日志* n））和日志* n。

现在的问题是它们如何相互比较。一般来说，某些函数的 log总是会比函数本身增长得慢，前提是函数随着函数的变大而不断增长。使用 log k < k 对于所有 k ≥ 1 的事实，如果我们选择任何 n ≥ 2 ^{2 2 2 2}，我们将得到 log* n ≥ 4，所以 log log* n ≥ 2，所以 log log log* n ≤ log* n，这给了我们 log log log* n = O(log* n)。从那里，不难证明 log log* n = O(2 ^{log* n} )。