2011年3月15日 星期二

[Introduction To Algorithms] 第四堂: Divide-and-Conquer(2)

第一堂課去台北參加 VS2010 C++ 開發日,聽錄音檔後再補,今天講的主要介紹,估算 asymptotic notation 的方法 -- The substitution method 。


這方法有兩個步驟,
1. Guess the solution  (猜)
2. Use induction to find constants and show the solution works (建構式歸納法)


觀念上和數學歸納法一樣,只是因為是 asymptotic notation 所以像是 boundary case 就不是那麼重要(immaterial) (時間函數是單調遞增)。
base case 也不用證明,只要
對 ο: c 挑足夠大
對 Ω: c 挑足夠小
這樣就可以蓋過 base case










在推導的過程中,若是遇到天花板、地板的證明就很惱人,要多一些調整的式子。
















Big-O 的證明還好,但是Ω 的證明就很麻煩(tedious)了。


所以老師補充了 smooth 的 Lemma 最後推導出只要是 poly 和 對數函數,都可以省略天花板和地板
但是,指數函數就不能夠省略。










證明過程請參考 p.21 ~ p.27 。
p.26 頁說明如何估算指數函數有天花板地板的 T(n)




















注意 smooth 的條件
1. 單調遞增
2. f(cn) = O(n)
因為是單調遞增,且 smooth,所以  bk 和 bk+1 看起來是 smooth,不會像上一張圖有跳 tone 的感覺。








這張投影片說明如果是用 asymptotic notation 表示 recurrence ,有何差異,結論是沒甚麼差, θ(n)=cn 這時的 c 是已知,推導下來只要 d 夠大就沒問題了。下張投影片是簡潔的寫法,不過要寫的精確也是要沒問題的啦!















沒有留言:

張貼留言