我想弄清楚f(n)=n^(logb(n))是否在Theta(n^k)中，因此增长为多项式，还是在Theta(k^n)中，因此增长为指数。
首先，我尝试简化函数:f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n))和1/log(b)是常数，我们得到f(n)=n^log(n)。
但是现在我被卡住了。我的猜测是f(n)在Theta(n^log(n))中呈指数级增长，甚至是超指数级增长，因为指数log(n)也在增长。
您可以将n^(log(n))写成(k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)).因为(log(n))^2 < n对于n足够大，那么这意味着n^(log(n))将比k^n增长得慢
尝试用b^m替换n，这使得logb(n) = m。
似乎不是 θ(指数)或 θ(多项式);上面的海报说明了为什么它不是指数型的。它不是多项式的原因可以用一个简单的反例证明。
证明n^logn不等于O(n^k):
- 假设存在k, c和n_0使得当n>n_0时，c*n^k>n ^log n.这就是O(n^k)的定义。
- 很容易找到一个n，用常量，这样就不成立了。
- 如果c>1，则n = (ck)^ck。
- 如果c<1，则n为k^k。