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。