還有底下題目比較難

有個東西先背起來

lim f(x)/g(x)=0，就代表f(n)=O( g(n) )

lim f(x)/g(x)=C > 0(C是一個常數)，就代表f(n)=Θ( g(n) )

lim f(x)/g(x)=∞，就代表f(n)=Ω( g(n) )

上面還有x趨近於無限大~~不好打出來顯示在網頁上~自己要知道

這個怎麼背?，其實你拿到題目馬上分哪個是f(n)，哪個是g(n)，然後帶入lim公式

就可以了，不用擔心分錯，不會怎麼樣

反正就是背，兩者取極限之後，是0還是常數，還是無限大

-----------------------------

首先是，Big-O

比較麻煩的題目像是

2ⁿ+n⁴的Big-O是多少

通常看到這樣的題目，其實答案不是O(2ⁿ)就是O(n⁴)

這等一下再講，先來看另外一件事情

常看到定義f(n)=O( g(n) )

其實就是在講，我n很大的時候，f(n)會大於g(n)

所以可以利用上面叫你背的來做題目

簡單舉例一題，f(n)=n+2、g(n)=2n

則limit的x趨近於無線大的 n+2 / 2n

就會變成lim ∞/∞ 這不就變成了需要用羅畢達法則

讓原式( lim n+2 / 2n )上下微分，變成 lim 1/2 就變成了 0.5，也就是一個常數

所以可以得到lim f(x)/g(x)=C > 0(C是一個常數)

也就是f(n)=Θ( g(n) )

回到2ⁿ+n⁴的Big-O是多少這種題目

像我直覺就是f(n)=2ⁿ，g(n)=n⁴

然後做 lim f(n)/g(n)

發現又都是無限大，上下取微分

啥?不會微?...微積分去重修- -................沒啦~開玩笑XD

2ⁿ對n取微分變成 2ⁿ* ln2 (ln2是natural-log 2阿~別搞錯)

然後 n⁴取微分...這該會了吧，4*n³

所以會變成lim (2ⁿ* ln2) / 4*n³

然後一樣都是分子分母無限大，再繼續微分，但你有沒有發現到，分子怎麼微都會留著2ⁿ (那個ln2是常數，學過微積分的都知道要比較極限常數可以丟了)

而分母的4*n³再微就變成12*n²然後一路為最後一定變成常數，不相信可以繼續微- -....

所以你一定會得到lim 2ⁿ / n⁴ 最後變成了lim (2ⁿ* (ln2)⁴) / 24 ，取極限就變成了 無限大，所以得到lim f(x)/g(x)=∞

就代表f(n)=Ω( g(n) )，所以2ⁿ=Ω( n⁴ )，其實你也可以寫 n⁴=O( 2ⁿ) 也是可以

所以這樣題目不管是Big-O或是Ω都會做了吧...重要是微積分最好不要忘記...

測試題：

a. logN屬於O(N^1/2)對或不對?

b. N ² /logN = Θ( N ² )

先寫到這邊

有疑問在問我