函数之间的复杂性渐近关系(θ，Big，little，Big，Complexity )

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->无穷)相互关联的: theta，Big，little，Big，asymptotically？请描述精确的解决方法，而不仅仅是最终的结果。
2. 原木基(即: 0.5，2，10，log n或n)是否影响结果？如果没有-为什么？如果是-怎么做？
3. 我想知道在任何实际(即使是假设的)应用程序中，复杂性性能是否与上面的f(n)或g(n)相似。请给出案例描述--如果存在的话。

我试着用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 +停止条件