complexity-theory - f(n)=n^log(n) 复杂度多项式或指数

Question

我试图弄清楚f(n)=n^(logb(n))是 inTheta(n^k)并因此增长多项式或 inTheta(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)也在增长。

Answer 1

你可以写成n^(log(n))因为(k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)).对于(log(n))^2 < nn 足够大，那么这意味着它n^(log(n))会比 k^n 增长慢

Answer 2

似乎不是theta(exponential)或theta(polynomial)；上面的海报显示了为什么它不是指数级的。它不是多项式的原因可以通过反例的简单证明来完成。

证明 n^logn 不是 O(n^k)：

• 假设有一些 k，有一些 c 和 n_0，使得对于 n>n_0，c*n^k > n^log n。这是 O(n^k) 的定义。
• 很容易找到带有常数的 an，这样这不成立。
• 如果 c>1，则 n 为 (ck)^ck。
• 如果 c<1，则 n 为 k^k。

Answer 3

尝试用 替换n，b^m这使得logb(n) = m. 这应该让你知道去哪里。