[Introduction To Algorithms] 第二堂: Growth of Functions(2)

這堂課先複習了利用微積分找極限的觀念來定上下界。 (p.14)
注意 Asymptotic Notation 與 微積分、集合的關西。

講到了集合，接下來就利用集合的理論對 Asymptotic Notation 做了一些推導:


結論就是: θ是 equivalence relation，而 Ο 是 partial order 的關西(同理類推其他的 notation)。

partial order 也就是可以比大小。




















當我們說 2n² = θ(n²) 時，這裡的 = 是屬於的意思，所以不可以對調。但每個教科書或論文的定義多多少少都有些差異，所以要注意上下文的關西。

老師花了蠻多時間在講這張投影片，等號左邊是 "對每一個"、等號右邊是 "存在"，把握集合的概念就可以了。

這張投影片老師用了一個例子說明，當最高次項都一樣時可以比較其係數這時候就可以用:
2n² + cn = 2n² + θ(n) 的方式來讓最高次項的係數表示出來。


這張投影片也解釋了第二章 p.21 頁 cn 表示的問題，因為 θ是 equivalence relation 所以用 cn 來表示 θ(n) 是 OK 的。 但是 Ο 就不行這樣用。

• T(n) = 2T(n/2) + θ(n)
• T(n) ≦ 2T(n/2) + Ο(n)

    掰!