老師補充了
- Rule of Sum
- Rule of Product
這裡要注意一下,為什麼第一個式子成立,但第二個式子卻不成立。答:係數的問題。第一個式子 c 可以從 θ 拿過來。但第二個式子因為是加法,最高項的係數固定是 1 。 所以會有問題。
接下來老師花了一些時間證明 Rule of sum
這裡用三個單向來證明,舉例來說要證明 A=B=C ,用三個單向就是
- A ≦ B
- B ≦ C
- C ≦ A
值得注意的是, for sufficient large n 這裡有三個 n0 要 n 要大於他們。但為了方便起見,用足夠大寫比較簡潔。
下面是一個 Rule of Sum 亂用的例子。
記住: 要用 asymptotically nonnegative function,而 max 的第二個 function 不管你 n 多大都無法是正數。
這張投影片才是正確的示範,不要亂用證明。
這個證明很有用,也很常用到,但注意不要亂用(等下會有投影片說明),Cormen 教科書上直接用,老師補充 Rule of Sum (什麼是θ相加)對於這個定理的證明推倒之理解比較有幫助。
這張也是講亂用的例子,這裡錯的原因是因為,這錯誤的式子用到多個 n0 個與 c0 ,記住要合併的話必須要找出共用的 n0 與 c。
p.32~p33 有舉例說明這個問題,可以參考。
接下來兩張投影片的 Theorem 比較少用,但是還是要注意一下,這張講的是 -1 在次方向時 ο與 Ω 要互換。這跟分數的比較大小很像。
這裡要注意,式子左邊代表的不是集合的集合。
而是要再 Union 起來。跟一般的不太依樣,要注意。
階層的話要注意 Stirling's formula,講義舉了三種方式證明,Summation 的證明方式很重要!!
Harmonic number 也蠻常用的。
有用到再複習吧!! 我的微積分阿~~
下面是一個 Rule of Sum 亂用的例子。
記住: 要用 asymptotically nonnegative function,而 max 的第二個 function 不管你 n 多大都無法是正數。
這張投影片才是正確的示範,不要亂用證明。
這個證明很有用,也很常用到,但注意不要亂用(等下會有投影片說明),Cormen 教科書上直接用,老師補充 Rule of Sum (什麼是θ相加)對於這個定理的證明推倒之理解比較有幫助。
這張也是講亂用的例子,這裡錯的原因是因為,這錯誤的式子用到多個 n0 個與 c0 ,記住要合併的話必須要找出共用的 n0 與 c。
p.32~p33 有舉例說明這個問題,可以參考。
接下來兩張投影片的 Theorem 比較少用,但是還是要注意一下,這張講的是 -1 在次方向時 ο與 Ω 要互換。這跟分數的比較大小很像。
這裡要注意,式子左邊代表的不是集合的集合。
而是要再 Union 起來。跟一般的不太依樣,要注意。
- 3.2 Standard notations and common functions
階層的話要注意 Stirling's formula,講義舉了三種方式證明,Summation 的證明方式很重要!!
Harmonic number 也蠻常用的。
有用到再複習吧!! 我的微積分阿~~
沒有留言:
張貼留言