函数之间的复杂度渐近关系(θ，大O，小O，大Omega，小Omega)

Question

让我们定义：

Tower(1) of n is: n.
Tower(2) of n is: n^n (= power(n,n)). 
Tower(10) of n is: n^n^n^n^n^n^n^n^n^n.

并给出了两个函数：

f(n) = [Tower(logn n) of n] = n^n^n^n^n^n^....^n (= log n times "height of tower").
g(n) = [Tower(n) of log n] = log(n)^log(n)^....^log(n) (= n times "height of tower").

三个问题：

1. 函数f（n）/g（n）是如何渐近相关的（n->无穷大），用θ，大O，小O，大欧米茄，小欧米茄？请描述解决方案的确切方式，而不仅仅是最终结果。

2. 对数的基数（即：0.5、2、10、对数n或n）是否影响结果？如果没有，为什么？如果是，如何？

3. 我想知道在任何真实的（即使是海波）应用程序中，复杂性性能是否与上面的f（n）或g（n）相似。请提供案例描述（如果存在）。

p.S。我试图替换：log n=a，因此：n=2^a或10^a。并对接收到的"塔"的高度计数感到困惑。

Answer 1

我不会给你提供解决方案，因为你必须做家庭作业，但可能还有其他人对一些提示感兴趣。

1） 数学：

log(a^x) = x*log(a)

• 这将使你的问题人性化

2） 数学：

logx(y) = log2(y) / log2(x) = log10(y) / log10(x)

• 当然：如果x是常数=>log2(x)和log10(x)是常数

3） recursive+停止条件