The Divide-and-Conquer Strategy

Presentation on theme: "The Divide-and-Conquer Strategy"— Presentation transcript:

1 The Divide-and-Conquer Strategy
(個各擊破)

2 演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破)
binary Searching、Quick Sort…. The Greedy Method(貪婪演算法) Prim MST、Kruskal MST、Djikstra's algorithm Dynamic Programming(動態演算法) 二項是係數、矩陣連乘、最佳二元搜尋樹… Trace Back(回溯) 圖形著色、漢米爾迴路問題…. Tree Searching Strategy(樹的追蹤)

3 個各擊破演算法簡介 將ㄧ個問題切成兩個或以上的較小問題，分別來解決。 如果較小的問題可以被解決的，即原問題的解可以藉由合併小問題的答案獲得。
是一種由上而下（top-down）的解題方式。 類似遞迴程式的方法解決問題。

4 Divide-and-Conquer問題介紹
二元搜尋法 合併搜尋法 Divide-and-conquer技巧 快速排序法(分割交換排序法) strassen的矩陣相乘演算法 大整數的計算 何時不能使用Divide-and-Conquer

5 Recursive（遞迴） 一個副程式或函數重複的呼叫自己本身，稱為遞迴(Recursive)。 利用遞迴解決問題，既經濟又方便。
可用遞回來解決的問題，那它也一定可轉成利用非遞迴的方式解決之。 撰寫遞迴時，千萬小心，一定要有一個結束點，否則後果嚴重。 遞迴在執行時，會藉助堆疊將呼叫本身函數的下一個敘述位址儲存起來，待執行完結束點後，再將堆疊的資料一一的彈出來處理。

6 遞迴設計步驟 發展從一個或多個較小實例的解中得到較大實例的解之方式。 決定分割為較小實例的終止條件。 決定終止條件時的解。

7 階乘 求n!，一般可能用的規則： 利用迴圈： 利用遞迴： n! = n * (n-1)!; ans = 1;
for (i = 2; i <= n; i++) ans = ans * i; 利用遞迴： int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */

8 遞迴呼叫流程圖 n=4 fact(3) … y=fact(2) fact(2) y=fact(1) fact(1) y=fact(0)
int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ n=4 fact(3) … y=fact(2) fact(2) y=fact(1) fact(1) y=fact(0) fact(0) Return(1) fact(4) y=fact(3) n=3 n=2 n=1 n=0 Fact(0)=1 Fact(1)=1 Fact(2)=2 Fact(3)=6 Fact(4)=24

9 遞迴呼叫流程圖 練習：fact(5)的呼叫過程，遞迴呼叫流程圖為何。 n=5 int fact(int n) { int x, y;
if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ n=5

10 遞迴推疊圖 (The recursive stack)
呼叫過程: f4 f3 f2 f1 f0

11 The stack at various times during execution during execution.
y (i)printf(“%d”, fact(3)) The stack at various times during execution during execution. (An asterisk indicates an uninitialized value.)

12

13 費氏數列 費氏數列 (Fibonacci number)： 利用遞迴範例： int fib(int n)
f(0) = 0;* f(1) = 1; f(2) = f(1) + f(0); f(3) = f(2) + f(1); ： f(n) = f(n-1) + f(n-2); 利用遞迴範例： int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */

14 遞迴呼叫流程圖 n=4 fib(4) … x=fib(3) fib(3) … x=fib(2) y=fib(1) y=fib(2)
fact(2) … x=fib(1) y=fact(0) fib(1) Return(1) n=2 n=1 fib(1)=1 fib(2)=1 fib(0) Return(0) n=0 fib(0)=0 n=3 fib(3) … x=fib(2) y=fib(1) fib(3)=2 n=1 fib(1) Return(1) n=4 fib(1)=1 fact(2) … x=fib(1) y=fact(0) fib(1) Return(1) n=2 n=1 fib(1)=1 fib(2)=1 fib(0) Return(0) n=0 fib(0)=0 int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ fib(4)=3

15 遞迴推疊圖 (The recursive stack)
呼叫過程: f1 f2 f3 f4 f0

16 遞迴推疊圖 練習：fib(5)的呼叫過程，請用樹狀結構來表示。 n=5 int fib(int n) { int x, y;
if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ n=5

17 遞迴推疊圖 f5 f1 f2 f3 f4 f0 呼叫過程:

18

19

20 何時不要使用遞迴？ 遞迴雖然可以使用少數幾行的敘述就可以解決一些複雜的問題，但有些問題會使用更多的執行時間。
以費氏數列為例： 遞迴之複雜度為O(2n)，而迴圈只要O(n)。 約需時2n/2

21 結論 以階乘為例：無論使用遞迴或迴圈，複雜度階為O(n)。 但遞迴需要較大的記憶體空間。 結論：
執行過程不像灌木，而是一直線的前進與後退，如：階乘，亦不適用遞迴。 以迴圈會使程式困難設計時，可考慮用遞迴。

22 結論 由於非遞迴使用了較多的區域變數（local variable），所以直覺上以為遞迴會較好，其實不然，因為遞迴使用了更多的時間存放暫時的結果，所以實際上遞迴花了更多的時間，因此，類似此種遞迴樹相當簡單，有如一條通道的，建議您還是使用非遞迴較佳。

23 A general divide-and-conquer algorithm
Step 1: If the problem size is small, solve this problem directly; otherwise, split the original problem into 2 sub-problems with equal sizes. Step 2: Recursively solve these 2 sub-problems by applying this algorithm. Step 3: Merge the solutions of the 2 sub problems into a solution of the original problem.

24 個各擊破演算法設計步驟 分割（Divide）一個較大問題實例成為一個或多個較小的實例
解出每個較小實例的答案（Conquer），除非實例已經分割到足夠小的地步，否則使用遞迴來解。 必要的話，將兩個較小實例的解答合併（Combine）已獲得原始問題實例解答。

25 二元搜尋法(Binary Search) 二元搜尋是應用於已排序好的資料，每次取所選定範圍資料的中位數(middle)來做比較。

26 二元搜尋法方法 假設串列依鍵值大小排列，使得 list[0].key <= list[1].key <= .....<= list[n-1].key。 此法是由比較 searchnum 和 list[middle] 開始，其中 middle = ( n-1 ) / 2 。其搜尋的結果可能有三種　　　 searchnum < list[middle].key 此種情況，放棄介於 list[middle] 和 list[n-1] 之間的記錄，繼續搜尋介於 list[0] 和 list[middle  - 1] 之間的記錄。　　　 searchnum = list[middle].key 在此種情形下，搜尋成功地結束。　　　 searchnum ＞ list[middle].key此種情況，放棄介於 list[0] 和 list[middle] 之間的記錄，繼續搜尋介於 list[middle+1] 和 list[n - 1] 之間的記錄。

27 設計步驟 分割這個陣列。 利用辦斷尋找值是否位於這個子陣列中，使用遞迴方式來完成，由分割子陣列的解答求得。
分割（Divide）一個較大問題實例成為一個或多個較小的實例 解出每個較小實例的答案（Conquer），除非實例已經分割到足夠小的地步，否則使用遞迴來解。 必要的話，將兩個較小實例的解答合併（Combine）已獲得原始問題實例解答。

28 二元搜尋法(遞迴版)

29

30 最差情況的時間複雜度(二元搜尋法,遞迴版)
基本運算：x與S[mid]的比較 輸入大小：n，陣列中的項目數量 O(n)=logn

31 Two-way merging 指的是將兩個以排序的陣列合併成一個以排序的陣列

32 合併排序法 構想為將兩個或兩個以上已排序好的檔案，合併成一個大的已排序好的檔案。
而在一維陣列的資料中，我們可以首先將資料分為兩個兩個一組，每組排序好後再合併為四個四個一組，然後再八個八個一組，依此類推。 Input 18 2 20 34 32 12 6 16 第1回合 第2回合 第3回合

33 設計步驟 分割這個陣列成為兩個具有n/2個項目的子陣列。 藉由排序以解答每個子陣列，除非陣列夠小，否則使用遞迴方式來完成。
將子陣列合併成一個已排序的陣列以合併子陣列的解答。 分割（Divide）一個較大問題實例成為一個或多個較小的實例 解出每個較小實例的答案（Conquer），除非實例已經分割到足夠小的地步，否則使用遞迴來解。 必要的話，將兩個較小實例的解答合併（Combine）已獲得原始問題實例解答。

34 合併排序

35

36 合併

37

38 最差情況的時間複雜度(合併) 基本運算：比較U[i]與V[ j ] 輸入大小：h與m，分別為兩輸入陣列的項目個數
W(h,m)為merge()的時間複雜度 W(h,m)=h+m+1

39 最差情況的時間複雜度(合併排序) 基本運算：發生在merge中的比較 輸入大小：n，陣列S中的項目個數
W(n): mergesort()的複雜度 W(n)=將U排序所發的時間+將V排序所發的時間+U與V合併所發的時間

40

41 遞迴方程式

42

43 快速排序(Quicksort) 又稱為劃分交換排序(partition exchange sorting)。
就平均時間而言，快速排序是所有排序中最佳的。 O(n log n)；不穩定性排序。

44 快速排序

45 樞紐(pivot)

46 分割

47 分割

48 樞紐

49 分割時間複雜度(Partition) 基本運算：發生在merge中的比較 輸入大小：n=high-low+1，也就是在子陣列中的項目數
因為除第一個項目外，每個項目都會被比較 T(n)=n-1 因此我們使用n來代表子陣列的大小而非陣列S的大小。只有當partition在最上層被呼叫時，它才代表S的大小

50 快速排序最差情況的時間複雜度(QuickSort)
是QuickSort的最差情況(Big O)

51 平均情況的時間複雜度(快速排序) 基本運算：在paritition副程式中，S[i]與pivotitem的比較

52 練習 S 29,14,15,1,6,10,32,12 finding the maximum of a set S of n numbers

53 設計步驟 分割這個陣列成為兩個具有n/2個項目的子陣列。 藉由排序以解答每個子陣列，除非陣列夠小，否則使用遞迴方式來完成。
將子陣列的答案比較找出一個最大數以合併子陣列的解答。 分割（Divide）一個較大問題實例成為一個或多個較小的實例 解出每個較小實例的答案（Conquer），除非實例已經分割到足夠小的地步，否則使用遞迴來解。 必要的話，將兩個較小實例的解答合併（Combine）已獲得原始問題實例解答。

54 結果

55 Time complexity Time complexity: Calculation of T(n): Assume n = 2k,
T(n) = 2T(n/2)+1 = 2(2T(n/4)+1)+1 = 4T(n/4)+2+1 : =2k-1T(2)+2k-2+…+4+2+1 =2k-1+2k-2+…+4+2+1 =2k-1 = n-1

56 Strassen(矩陣相乘) 將較大矩陣分成較小矩陣盡興乘法運算 在大矩陣相乘時，複雜度比直接矩陣相乘的好

57 一般的矩陣相成演算法 Strassen 發表了一個矩陣相乘演算法，複雜度比 O(n3) 好 矩陣相乘O(n3)
void mul(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n) { int i, j, k, sum; for (i=0; i < n; i++) for (j=0; j < n; j++) sum = 0; for (k=0; k < n; k++) sum = sum+a[i][k]*b[k][j]; c[i][j] = sum; } 矩陣相乘O(n3) Strassen 發表了一個矩陣相乘演算法，複雜度比 O(n3) 好

58 Strassen矩陣相乘設計

59 運算次數比較

60 分割

61 分割

62 Example

63 Example

64 Strassen 演算法

65 Strassen的時間複雜度分析 基本運算：一個基本的乘法 輸入大小：n，也就是這些矩陣的列數與欄數

66 兩個演算法在n‧n矩陣相成的比較

67 大整數的乘法

68

69 大整數乘法

70 最差情況的時間複雜度(大整數的乘法) 基本運算：當相加、相減、或執行 時，一位數字(以十進位表示)的操作
輸入大小：也就是兩個大整數u、v的位數

71 何時不能使用Divide-and-Conquer
一各大小為n的個體被分成兩個或更多大小接近n的個體。 一各大小為n的個體被分成n個大小為n/c的個體，其中c為常數。 參考何時不要使用遞迴