算法分析中的費率？

Question

爲什麼對數增長比任何多項式都慢？這是什麼（可以理解的）證明？

同樣，

爲什麼總指數增長比任何多項式快？

Answer 1

編輯：這個答案基本上是在做一下彭一說的。

我們採取的

log_2(x)/x^p 

的限制常數p> 0，表明極限是零。既然log_2（x）和x^p隨着x增大而無限制地變爲無窮大，我們應用l'Hopital's rule。這意味着我們的限制是一樣的

1/(x*ln2)/p*x^(p-1) 

使用分數簡單規則的限制，我們減少了這

1/(p * x^p * ln2) 

由於分母趨於無窮大，而分子是不變的，我們可以評估極限 - 它是零，這意味着log_2（x）漸近地比x^p漸近地增長，而不管p的（正）值如何。

EDIT2：

順便說一句，如果你有興趣在這個問題和發佈答案，不妨考慮通過以下鏈接，並提交到運動的新計算機科學StackExchange現場支持：

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

Answer 2

給定兩個（非負）實值函數f和g，要計算

lim_{x -> infinity} f(x)/g(x) 

此限制是：

• 0當且僅當f增長慢於g
• infinity當且僅當f增長快於g
• c對於某一常數0 < c < infinity當且僅當f和g增長以相同的速度

現在，你可以把你喜歡的任何實例和計算的極限，看看哪個生長較快。

Answer 3

你可以考慮衍生品。

d（X^N）/ DX = NX ^（N-1）

d（LN X）/ DX = 1/X

對於n> = 1 NX ^（n-1個）隨x增加或保持不變，而1/x隨x減小，所以多項式增長更快。

e^x的對數是x，而n^x的對數是n ln x，所以用上面的參數來比較e^x的對數和x^n的對數，e^x增長更快。