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代替b^m，这会使logb(n) = m代替。这应该让你知道去哪里。

Answer 2

你可以写n^(log(n))作为(k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)).由于(log(n))^2 < n对于n足够大，那么这意味着n^(log(n))将增长大于k慢^ N

Answer 3

好像它不是THETA（指数）或THETA（多项式）;上面的海报显示了为什么它不是指数。不是多项式的原因可以通过反例来证明。

证明是n^LOGN不是为O（n^K）：

• 假设有某个k，与一些c和N_0使得对于n> N_0，C * N^K> N R个日志这是O（n^k）的定义。
• 很容易找到一个有常数的n，这样就不成立。
• 如果c> 1，那么n是（ck）^ ck。
• 如果c < 1，那么n是k^k。