第一堂課去台北參加 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 夠大就沒問題了。下張投影片是簡潔的寫法,不過要寫的精確也是要沒問題的啦!
沒有留言:
張貼留言