Course 5 切割與征服 Divide-and-Conquer

▓ Outlines 本章重點 Divide-and-Conquer策略的描述 Binary Search Merge Sort Quick Sort Strassen‘s 矩陣相乘演算法 何時不能使用 Divide-and-Conquer

▓ Divide-and-Conquer策略的描述與技巧 Divide-and-conquer 是一種由上而下 (top-down) 的解題方式. 它將一個問題切割 (divides) 成兩個或以上的較小問題。較小的問題通常是原問題的實例。 如果較小的問題之解可以容易地獲得，那麼原問題的解可以藉由合併較小問題的答案獲得。 如果小問題還是太大以致於不易解決，則可以再被切割成更小的問題直到切到夠小而易獲得結果為止。

Def: 可將母問題切割成較小的問題 (切割)，使用相同的解決程序加以處理 (征服)。所有小問題的解可以成為母問題的最後解; 若有必要，則再將每個小問題的處理結果加以合併，就可以得到最後的答案。 由於使用相同的解決程序處理每個小問題，這一個程序就會被遞迴呼叫，因此一個遞迴演算法則通常以一個副程式的型式出現，內部包含一個解決程序與遞迴呼叫。 對於具有遞迴關係的問題，或是一些採用遞迴定義的資料結構，都適合採用Divide-and-Conquer演算法設計策略 最簡潔、易懂 效率差 (∵採用遞迴設計)

Divide-and-Conquer使用時機 問題本身具有遞迴關係 母問題可被切割成較小的 “相同” 問題 如: 階乘問題、費氏數問題、河內塔問題、快速排序問題、二元搜尋問題…等 資料結構屬於遞迴定義 大量的Data Set，在切割後仍為一組具 “相同性質” 的Data Set 如: 二元樹 (Binary Tree)、鏈結串列 (Link List)…等

遞迴演算法則的設計 找出問題的終止條件. 找出問題本身的遞迴關係 (遞迴呼叫). 技巧: 思考遞迴呼叫需要哪些參數? 遞迴呼叫的傳回值為何? 遞迴呼叫的終止條件為何? 終止傳回何值? Procedure Recursion_subroutine(Parameter); { if (終止條件) then Return( ); else Recursion_subroutine(New_parameter) ; }

▓ Binary Search (二分搜尋) 實施前提: 觀念: 檔案中記錄須事先由小到大排序過 須由Random (或Direct) access之機制支援 (e.g., Array) 觀念: 每次皆與Search範圍的中間記錄進行比較!! while ( l  u ) 比較 (k, S[m]) case “=”: found, i = m, return i; case “<”: u = m-1; case “>”: l = m+1; recurn 0; l m u middle l m u S 小 大 //找到了 //要找的資料在左半部 //要找的資料在右半部

分析 利用Time function T(n) = T(n/2) + O(1) = T(n/2) + c = (T(n/4 + c)) + c = T(n/4) + 2c = (T(n/8) + c) + 2c = T(n/8) +3c = … = T(n/n) + log2nc = T(1) + c log2n (T(1) = 1, c 為大於 0 的常數) = 1 + c log2n  T(n) = O(log2n)

二元搜尋法的步驟摘要如下。如果x與中間項相同則離開，否則: 切割 (Divide) 該陣列成大約一半大小的兩個子陣列。. 如果x小於中間項，選擇左邊的子陣列。如果x大於中間項，則選擇右邊的子陣列。 藉由判斷x是否在該子陣列中來征服 (Conquer; 或稱解決 solve) 該子陣列。 除非該子陣列夠小，否則使用遞迴來做這件事。 由子陣列的解答來獲得 (Obtain) 該陣列的解答。 二元搜尋法是最簡單的一種Divide-and-conquer演算法。因為原有問題的解答就是較小問題所解出的解答，所以沒有輸出結果的合併。

▓ Merge Sort (合併排序) 觀念: 可分為兩種類型: 將兩個已排序過的記錄合併，而得到另一個排序好的記錄。 Recursive (遞迴) Iterative (迴圈, 非遞迴)

Recursive Merge Sort (遞迴合併排序) 將資料量 n 切成 n/2 與 n/2 兩半部，再各自Merge Sort，最後合併兩半部之排序結果即成。 切割資料量 n 的公式為: [ ]: Run, 已排序好的檔案記錄 Run的長度: Run中記錄個數

Stack 第四層切割所有 資訊依序輸入 第三層切割所有 資訊依序輸入 第二層切割所有 資訊依序輸入 第一層切割所有 資訊依序輸入

Avg. / Worst / Best Case: O(n log n) 以Recursive Merge Sort角度: [說明]: Time-Complexity Avg. / Worst / Best Case: O(n log n) 以Recursive Merge Sort角度: [說明]: 時間函數: T(n) = T(n/2) + T(n/2) + cn 時間複雜度求法: 遞迴樹 步驟: 將原本問題照遞迴定義展開 計算每一層的Cost 加總每一層的Cost即為所求 數學解法 左半部遞迴 右半部遞迴 最後合併左右兩半部所花時間 ∵ 左、右半部排好之後，各只剩一個Run，且兩半部各有n/2的資料量，其最後一次合併時的比較次數 “最多”為 n/2 + n/2 -1 次，即約 n-1 次 (slide 72) 時間的表示可為 cn 次(∵為線性時間))

合併排序法包含了下列的步驟 : 切割 (Divide) 該陣列成為兩個具有 n/2 個項目的子陣列。 征服 (Conquer; 或稱解決solve)每一個子陣列。 除非該子陣列夠小，否則使用遞迴來做這件事。 合併 (Combine) 所有子陣列的所有解答，以獲得主陣列的解答。

▓ Divide-and-Conquer 技巧 征服 (Conquer ; 或稱解決solve) 每一個較小的問題。 除非問題已經足夠的小，否則使用遞迴來解決。 如果需要, 將所有小問題的解答加以合併(combine) ，以獲得原始問題的解答。 需要合併的問題: Merge sort 不需要合併的問題: Binary search

▓ Quick Sort (快速排序) Avg. case 下，排序最快的algo. Def: 觀念: 將大且複雜的問題切成許多獨立的小問題，再加以解決各小問題後，即可求出問題的Solution。 此即 “Divide-and-Conquer” (切割並征服)的解題策略。 觀念: 將第一筆記錄視為Pivot Key (樞紐鍵 (P.K.) ，或稱Control Key)，在Pass 1 (第一回合) 後，可將P.K.置於 “最正確” 的位置上。 Ex: (經過Pass 1)  把P.K.擺在正確的位置 為切割的概念 (∴可使用遞迴) P.K. Ri Rj , Ri.key  P.K. 且 Rj.key  P.K. P.K.

多顆CPU時的運算過程:

Time-Complexity Best Case: O(n log n) [說明]: P.K.之最正確位置恰好將資料量均分成二等份 以Multiprocessor來看，2個CPU的工作量相等，工作可同時做完，沒有誰等誰的問題 [說明]: 時間函數: T(n) = cn + T(n/2) + T(n/2) 時間複雜度求法: 遞迴樹 步驟: 將原本問題照遞迴定義展開 計算每一層的Cost 加總每一層的Cost即為所求 數學解法 左半部 右半部 變數 i 與 j 最多花 n 個執行時間找記錄 (即: 決定P.K.最正確位置所花時間)

Worst Case: O(n2) [說明]: 或 當輸入資料是由大到小或由小到大排好時 (切割毫無用處) 輸入資料: 小 大 Pass 1 輸入資料: 小 大 Pass 1 P.K. [0筆] P.K. [ n-1筆 ] 輸入資料: 大 小 Pass 1 P.K. [ n-1筆 ] P.K. [0筆]

Average Case: O(n log n) [說明]:  , T(0) = 0 S筆 (n-S)筆 P.K.

▓ Strassen's Matrix Multiplication Algorithm 矩陣乘法問題 (Matrix Multiplication Problem): 給定兩個方陣A, B，其Size均為nn，其中n=2k。如果n不是2的冪次方，則可以增加額外的列與行，但是補上的元素都是零: 若矩陣是扁的，則可以在該矩陣下方補上數列的0，使之成為方陣 若矩陣是窄的，則可以在該矩陣右方補上數行的0，使之成為方陣 欲求C = A  B，傳統的矩陣乘法: c11 = a11 b11+a12 b21 c12 = a11 b12+a12 b22 c21 = a21 b11+a22 b21 c22 = a21 b12+a22 b22

遞迴方程式為: T(n) = 8T(n/2) +cn2 由支配理論可以得知該遞迴方程式最後可以得到(n3) 將矩陣乘法問題放大來看: C11 = A11 B11 + A12 B21 C12 = A11 B12 + A12 B22 C21 = A21 B11 + A22 B21 C22 = A21 B12 + A22 B22 遞迴方程式為: T(n) = 8T(n/2) +cn2 由支配理論可以得知該遞迴方程式最後可以得到(n3) Cij, Aij, Bij皆為子矩陣，即可 用遞迴切割的方式來將此矩 陣切割成數個小矩陣。

該演算法的時間複雜度為O(n3)，乘法運算比加法運算要來得多。 前例的乘法有8個，加法有4個。 然而，就系統執行的角度來說，乘法運算的複雜度遠超過加法運算，因此該演算法在實際執行的速度會更慢。

在1969年, Strassen 發表了一個時間複雜度較三次方演算法為佳 (time complexity is better than cubic)的演算法。

遞迴方程式為: T(n) = 7T(n/2) +cn2 由支配理論可以得知該遞迴方程式最後可以得到(nlg7)

▓ 何時不能使用 Divide-and-Conquer 一個大小為n的個體被分成兩個或更多個大小為接近n的個體. 一個大小為n的個體被分成n個大小為n/c的個體，其中c為常數.

有時，某些問題隨輸入範例的大小成指數成長是無法避免的。雖然此時Divide-and-conquer無法獲致良好的執行效率，但仍可採用。 河內塔問題每呼叫一次就需搬動圓盤一次，當圓盤的個數 n 是64時，總共需要搬動圓盤 264-1次，因此演算法的複雜度等級 (order) 是 O(2n) 即: 河內塔問題的圓盤搬動次序是與 n 成指數關係 但是經過証明上述河內塔問題的演算法，已經是給定該問題的限制下最佳的演算法則了。