Lecture 4 Recurrences 給定T(n)=T(n/2) + O(n) 我們該如何得到 T(n) = O(nlogn)? 本章的重點教導如何解上述的遞迴式。

4.1 The substitution method (ii)用歸納法證明 (for both upper and lower bounds) 猜的時候必須根據經驗， 當猜測的結果不對時，必須加以修正再重新證明一次。 Recurrences

範例: 找到 T(n) = 2T(n/2) + n 的 upper bound (T(1) = 1) 猜測 T(n) = O(nlg n) 試著證明存在著常數 c 和 n0 使得 T(n)  cn lg n 對於所有的 n  n0 都成立。 注意歸納法有兩個重要的步驟： Basis Induction Recurrences

在 n=1 時，沒有常數 c 能夠滿足 T(1)  cn lg n=0。 Basis: (n=n0) 在 n=1 時，沒有常數 c 能夠滿足 T(1)  cn lg n=0。 在 n=2 時，任何大於等於 T(n)/(n lg n) 的常數 c 都會滿足 T(n)  cn lg n。所以我們可以選擇 n0  2 且 c  T(n0)/(n0 lg n0) ………(1) Basis要說明的是當n小的時候成立 (n = n0) Recurrences

假設 T(n)  cn lg n 這個式子對於所有介在 n0 和 n-1 之間的 n 都成立。我們可以得到 Induction: (n>n0) 假設 T(n)  cn lg n 這個式子對於所有介在 n0 和 n-1 之間的 n 都成立。我們可以得到 T(n)  2(cn/2 lg n/2) + n (Substitution)  cn lg (n/2) + n = cn lg n – cn lg 2 + n = cn lg n – cn + n cn lg n， 其中最後一步在 c  1 的時候成立………(2) 根據(1)(2)，我們可以選擇 n0 = 2 以及 c = max{1， T(2)/(2 lg 2)} = 2 讓 basis 及 induction 都成立。 Induction則是要證明當n > n0的情況下成立 假設我們先前的假設在n0到n之間都成立，然後證明 T(n) 也符合先前的假設。 Recurrences

Substitution Method 步驟 1. 猜測 T(n) = O(g(n))  證明存在 c 和 n0 使得 T(n)  cg(n) 對於全部的 nn0 都成立……(1) Recurrences

 如果我們已知 c 和 n0，那麼我們就可以用歸 納法證明(1) (a) Basis step: (1) 在 n = n0 時成立 (b) Induction step: (1) 在 n > n0 時成立  如何找到 c 和 n0 符合歸納法中的證明？ (i) 找到符合 basis step 的 c 和 n0 的條件 (ii) 找到符合 induction step 的 c 和 n0 的條件 (iii) 綜合 (i) 和 (ii) 的條件 Recurrences

Subtleties: (修改假設：減一個低次方項) 範例: T(n) = T(n/2)+T(n/2)+1 (T(1) = 1) 猜測 T(n) = O(n) 當我們沒辦法根據先前的技巧順利得證的話，必要時得修改假設 subtleties就是修改假設的一個方法。 Recurrences

Induction: T(n) = T(n/2) + T(n/2) + 1  c(n/2 + n/2) + 1 Basis: ok! Induction: T(n) = T(n/2) + T(n/2) + 1  c(n/2 + n/2) + 1 = cn + 1 無法證明 T(n)cn !!!! 試著證明 T(n)  cn – b Induction: T(n)  (cn/2-b) + (cn/2-b) + 1 = cn – 2b + 1  cn – b， 最後一步對於任意大於等於 1 的常數 b 都成立 若無法證明 T(n) <= cn, 但是很接近了，要想想是否能證明 T(n) <= cn – b. Recurrences

Avoiding pitfalls: T(n) = 2T(n/2) + n 猜測 T(n) = O(n)。 試著證明 T(n)cn。 Induction: T(n)  2cn/2 + n  cn + n = O(n)  錯 !! 假設我們正在證明 T(n) <= cn, 對於 induction 來說，最後 T(n) 也必須要小於等於 cn 本頁中的式子只能導到 T(n) <= (c+1)n, 代表假設不成立。 Recurrences

Changing variable: T(n) = 2T( ) + lg n 為了簡單起見，假設 n=2m。變成 T(2m) = 2T(2m/2) +m 令 S(m) = T(2m)，我們可以得到 　 S(m) = 2S(m/2) + m (把 m 換成 lg n) 因為我們知道 S(m) = O(m lg m)，所以可以推得T(n) = O(lg n lglg n) 有時候遞迴式子直接分析不容易 透過變換變數，式子有可能會變得比較容易分析。 Recurrences

4.2 The iteration(recursion-tree) method 範例: T(n)=3T(n/4) + n T(n) = n + 3(n/4 + 3T(n/16)) = n + 3n/4 + 9(n/16 + 3T(n/64)) . . (note that n/( 1)  n + 3n/4 + 9n/16 + 27n/64 + ... + (1) = 4n+o(n) = O(n) 一直不斷地將遞迴式子帶入，最後就會得到一長串式子 分析該式子即可得到最後的結果。 Recurrences

Recursion trees: (for visualizing the iteration) T(n)=2T(n/2) + n2 Recurrences

n2 n2 lg n 畫成樹狀表示 然後將每一層所花的時間加起來就是全部所需要的時間。 … … Total： Recurrences

範例: T(n) = T(n/3) + T(2n/3) + n … … Total： Recurrences

4.3 The master method Theorem 4.1 (Master theorem) 令 a  1 及 b > 1 為常數，令 f(n) 為一函數，且定義 T(n) 為非負的整數，且其遞迴式為 T(n) = aT(n/b) + f(n)，在此 n/b 表示 n/b 或 n/b。則依不同的情況，T(n) 的大小範圍如下： 1. 若存在常數  > 0 使得 f(n) = O(nlogb a)，則 T(n) = (nlogb a) 2. 若 f(n) = (nlogb a)，則 T(n) = (nlogb a lg n) 3. 若存在常數  > 0 使得 f(n) = (nlogb a+)，且存在常數 c < 1 使得對所有夠大的 n，af(n/b)  cf(n)，則 T(n) = (f(n))。 在某些情況下，我們不需要大費周章的分析遞迴式 本小節提供了一些公式，只要符合提到的條件，就可以用公式直接求解。 要注意的是，Master Theorem所提供的這些公式仍有不能解決的遞迴式子。 Recurrences

範例: T(n) = 9T(n/3) + n, a=9, b=3, nlogb a= n2 套用 case 1，可得 T(n)=(n2) 範例: T(n) = T(2n/3) + 1, a=1, b=3/2, nlogb a= n0 套用 case 2，可得 T(n)=(lg n) 範例: T(n) = 3T(n/4) + n, a=3, b=4, nlogb a= nlog4 3 套用 case 3，可得 T(n)=(n) T(n) = 9T(n/3) + n => a = 9, b = 3 T(n) = T(2n/3) + n => a = 1, b = 3/2 T(n) = 3T(n/4) + n => a = 3, b = 4 Recurrences

註： 這三個 case 並沒有包含所有 f(n) 的可能性。 Case 1 與 2 之間有 gap, case 2 與 3 之間也有。 範例： T(n) = 2T(n/2) + n lg n 在這個例子中，第二個 case 以及第三個 case 都不能被套用。 Recurrences

Exercises Problem 1: 在德國的樂透中你必須從 1 到 49 號之中選出六個數字。玩樂透有一個很普遍的策略（雖然不會增加你贏的機會），就是選擇一個子集合 S 包含 49 個數字裡面的 k (k>6) 個數字，然後只從 S 裡面選擇 6 個數字，重複玩很多次。 例如，k=8 且 S={1,2,3,5,8,13,21,34}，總共有 28 種組合: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]。 你的工作就是寫一個程式，讀入 k 以及 S，然後印出所有可能的組合。 Recurrences

Exercises 輸入：有好幾組測資。每一組測資會先給一個整數 k (6 < k < 13)，接著之後的 k 個整數就是集合 S (數字由小排到大)。k=0 代表輸入結束。 輸出：對於每組測資，印出所有可能的組合（一行印一種組合）。每一種組合的數字要從小到大印出，每個數字之間要用一個空白隔開。所有的組合必須要根據字典順序印出，也就是先從最小的數字當作排序的依據，相等的時候再根據第二小的數字，依此類推。每一組測資的輸出要用一個空行隔開。不要在最後一組測資的輸出之後多印一個空行。 Recurrences

以下是一個輸出入的實例: Sample Input Sample Output 7 1 2 3 4 5 6 7 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 Recurrences

Exercises Problem 2: 產生排列組合在資訊科學方面一直是個重要的問題。這一題要求你把一段字串的所有排列組合依照字典順序由前到後排好。請記住你的演算法必須要有效率。 輸入：第一行包含一個整數 n， 接下來的 n 行包含了 n 個字串。字串只會由英文字母或數字所構成，而且不會有空白字元在裡頭。字串最大的長度為 10。 輸出：對於每組測資，依照先後順序把所有的排列組合印出來。字母的大小視為不同，而且要注意印出來的排列組合不能重複。在每組輸出後面要多印一個空行。 Recurrences

以下是一個輸出入的實例: Sample Input Sample Output 3 ab abc bca ab ba abc acb bac bca cab cba abc acb bac bca cab cba Recurrences