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

Question

我想弄清楚是否 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)也在增长。

Answer 1

你可以写 n^(log(n))如 (k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)).自 (log(n))^2 < n如果 n 足够大，那么这意味着 n^(log(n))会比 k^n 增长得慢