f（n）= n ^ log（n）复杂多项式或指数

2018-06-18 14:50:16

我试图找出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）的定义。

用常数找到一个这样的结果并不容易。

如果c> 1，那么n是（ck）^ ck。

如果c <1，那么n是k ^ k。

链接地址: http://www.djcxy.com/p/52491.html