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 < nn 足够大，那么这意味着将比n^(log(n))k^n 增长得慢

Answer 2

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