algorithm - 什么是函数之间的渐近关系

Question

我想知道以下给定关系的原因:

1. n < (log n)^log n
2. log log n = O(root(log n))
3. (log n) != omega(log(n!))
4. log(log*n) < log*(log n)

所有日志的基数是 2。显然我知道答案，但我不知道如何找到它们。我还可以看到，仅仅通过输入 n 的值是找不到这些的。每时每刻。至于第一个关系，它不适用于 n=2 .将上述函数应用于 n 的大值有什么影响？ ？任何人都可以提供通用解决方案(或指导我的方式)，以便我可以找到在 n 上应用上述(或未给出的额外功能)函数的不同组合的关系。 .例如，log*log(root(log(n!)))与 loglog*(log(root(n!)))

Answer 1

粗略地说，渐近意味着接近无穷大(因为函数接近其渐近线)。

所以为了粗略估计，使用非常大的 n。

有关更精确的定义和讨论，请参阅 Asymptotic Analysis ，或任何介绍计算机科学的文本。