2011年3月8日 星期二

[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 ,用三個單向就是

  • ≦ B
  • ≦ 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 也蠻常用的。


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

沒有留言:

張貼留言