[閒聊] O(n)大師請進 star123 PTT批踢踢實業坊

作者: star123 (光二比利海靈頓) 2019-10-01 17:26:02

為什麼 n^4 < n^2 * 2^n
我數學超爛的　救命　我不要寫數學==我是來上乘是客

作者: moonoftree (月之樹) 2018-10-01 17:26:00

因為 2^n 成長幅度比 n^4 快

作者: emptie ([ ]) 2019-10-01 17:27:00

兩邊同時除以n2

作者: matsubuff (竹內) 2019-10-01 17:27:00

指數比平方快

作者: surimodo (好吃棉花糖) 2019-10-01 17:27:00

取log

作者: moonoftree (月之樹) 2019-10-01 17:28:00

指數時間 > 多項式時間

作者: star123 (光二比利海靈頓) 2019-10-01 17:28:00

我不會log==

作者: surimodo (好吃棉花糖) 2019-10-01 17:31:00

2logn < nlog2 常數省略 logn < n不用log也行吧不過往忘記用啥方法了= =

作者: soulgem (あたしって、ほんとバカ) 2019-10-01 17:35:00

(1+1)^n 二項式展開一下就爆掉左邊了不然只要有一個 n^2 < 2^n, 就可以得到(n+1)^2 < 2^(n+1)

作者: star123 (光二比利海靈頓) 2019-10-01 17:48:00

我用emptie那個方法算出來了==謝謝你們

繼續閱讀