[闲聊] 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那个方法算出来了==谢谢你们

继续阅读