[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，所以  b^k 和 b^k+1 看起來是 smooth，不會像上一張圖有跳 tone 的感覺。

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