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

asymptotic notation 的運算也就是集合的運算。


老師補充了 

• Rule of Sum
• Rule of Product

當作範例說明。注意這兩個 theorem 在程式中的應用。(時間和 vs 巢狀迴圈)

這裡要注意一下，為什麼第一個式子成立，但第二個式子卻不成立。答:係數的問題。第一個式子 c 可以從 θ 拿過來。但第二個式子因為是加法，最高項的係數固定是 1 。 所以會有問題。

接下來老師花了一些時間證明 Rule of sum
這裡用三個單向來證明，舉例來說要證明 A=B=C ，用三個單向就是

• A ≦ B
• B ≦ C
• C ≦ A

這樣就證明出 A=B=C 了。 三個單向證明都很簡單參考 p.26~p.28。

值得注意的是， for sufficient large n 這裡有三個 n₀ 要 n 要大於他們。但為了方便起見，用足夠大寫比較簡潔。

下面是一個 Rule of Sum 亂用的例子。
記住: 要用 asymptotically nonnegative function，而 max 的第二個 function 不管你 n 多大都無法是正數。

這張投影片才是正確的示範，不要亂用證明。

這個證明很有用，也很常用到，但注意不要亂用(等下會有投影片說明)，Cormen 教科書上直接用，老師補充 Rule of Sum (什麼是θ相加)對於這個定理的證明推倒之理解比較有幫助。

這張也是講亂用的例子，這裡錯的原因是因為，這錯誤的式子用到多個 n₀ 個與 c₀ ，記住要合併的話必須要找出共用的 n₀ 與 c。
p.32~p33 有舉例說明這個問題，可以參考。

接下來兩張投影片的 Theorem 比較少用，但是還是要注意一下，這張講的是 -1 在次方向時 ο與 Ω 要互換。這跟分數的比較大小很像。

這裡要注意，式子左邊代表的不是集合的集合。
而是要再 Union 起來。跟一般的不太依樣，要注意。

• 3.2 Standard notations and common functions

p.38 ~ p.43 介紹了常用的 function 指數、對數、階層等等。微積分的基礎就很重要 (我忘得差不多了 = =) 概念性的像是 polynomials 代表的是上限為 poly 而不一定是指多項式函式。 Logarithms 再怎麼強都沒有poly 快。Logarithms的底沒有這麼重要 (用換底公式弄完後只是一個係數)。


     階層的話要注意 Stirling's formula，講義舉了三種方式證明，Summation 的證明方式很重要!!
     Harmonic number 也蠻常用的。


有用到再複習吧!! 我的微積分阿~~