分治算法（divide & conquer algorithm）

1、分治算法(Divide & Conquer Algorithm),宮秀軍天津大學計算機科學與技術學院gongxj@tju.edu.cn,提綱,分治法基本原理應用歸并排序快速排序選擇問題復雜性的下限最大最小問題的下限排序算法的下限,14.1 分治法思想,分治法設計算法的思想將問題分成(divide)多個子問題；遞歸地(conquer)解決每個子問題；將子問題的解合并(combine)成原問題的解。分治法常

2、常得到遞歸算法Merge-Sort, Quick SortDiscrete Fourier transform (FFT). 算法復雜性分析Master methodSubstitution method,例14-1 [找出偽幣],現(xiàn)有16個硬幣,其中有一個是偽幣，并且偽幣重量比真幣輕。試用一臺天平找出這枚偽幣。兩兩比較,最壞情形需8次比較找出偽幣。分治法僅需4次比較找出偽幣。,Compute an,Problem: Co

3、mpute an, where n∈N.Naive algorithm: Θ(n).Divide-and-conquer algorithm:an= an/2?an/2 if n is even;an =a(n–1)/2?a(n–1)/2?a if n is odd.ComplexityT(n)=T(n/2)+Θ(1)Master方法, a=1 b=2 Cas

4、e 2: logba=0,k＝0T(n)=Θ(lgn),例14-2 [金塊問題],問題有若干金塊試用一臺天平找出其中最輕和最重的金塊.等價于n個數(shù)中找出最大和最小的數(shù).直接求解1：先找出最大值,然后在剩下的n-1個數(shù)中再找出最小值.需2n-3次比較.,例14-2,直接求解2：最大最小值同時進行查找,func minmax( T a[], n, T &max , T & min){min←a[0];max←

5、a[0];For i←1 to n-1 do if a[i]max max←a[i]},當輸入數(shù)組為順序時,算法要做2(n-1)次比較當輸入數(shù)組為逆序時,算法要做n-1次比較,例14-2,分治法求解,int minmax-dc(T A[0,n-1], T & max, T &min)if n<1 max←min←a[0],return; else m←n/2

6、 minmax-dc (A[0,m-1],max1,min1), minmax-dc (A[m,n-1],max2,min2), max←max(max1,max2), min←min(min1,min2), return.,例14-2 （解續(xù)）,設c(n)為使用分治法所需要的比較次數(shù),假設n=2k則有: c(n)=1 ,n = 2 ;

7、 c(n)=2c(n/2)+2, n ≥ 2 .復雜性分析Master方法給出c(n)=Θ(n).迭代展開可得:c(n)= (3n/2)-2。,程序14-1 找出最小值和最大值的非遞歸程序,程序14-1 找出最小值和最大值的非遞歸程序,程序14-1 找出最小值和最大值的非遞歸程序,算法14.1分析,當n為奇數(shù)時,n=2m+1,比較m對相鄰元素, 比較次數(shù)為3*m=3*(n-1)/2

8、 =3n/2-3/2=[3n/2]-1/2-3/2 =[3n/2]-2 [ ]表示向上取整.當n為偶數(shù)時,n=2m,比較m-1對相鄰元素 比較次數(shù)為1+3*(m-1)=1+3*(n-2)/2 =1+3n/2-3 =[3

9、n/2]-2該算法所用比較次數(shù)最少,例14-3 [矩陣乘法],兩個n×n 階的矩陣A與B的乘積是另一個n×n 階矩陣C，C 的元素為: C(i, j)=∑kA(i, k)B(k, j),template ;void MatrixMulti( T** A, T**B, T** C, int n){ for (int i=0; i<n; i++) for

10、(int j=0; j<n; j++){ T sum=0; for (int k=0; k<n; k++) sum+=A[i][k]*B[k][j] c[i][j]=sum; }},假如每一個C(i, j)都用此公式計算,則計算C 所需要的運算次數(shù)為n3次乘法和n2(n-1)次加法.,矩陣乘法-分治法

11、,2×2分塊矩陣乘法,a,b,c,d,是A的4個(n/2)階子矩陣,e,f,g,h是B的4個(n/2)階子矩陣,矩陣乘法-分治法,基本觀點：n×n matrix = 2×2 matrix of (n/2)×(n/2) submatrices,8 mults of (n/2)×(n/2) submatrices,4 adds of (n/2)×(n/2) submatrices

12、,recursive,,復雜性分析T(n)=8T(n/2)+Θ(n2) （Θ(n2)－4個(n/2)階矩陣加法的計算時間）nloga=nlog8=n3 ? CASE 1?T(n)=Θ(n3),從分治法沒得到好處！,算法,基本觀點合并分塊矩陣以減少乘法次數(shù)2×2 矩陣相乘可用7次乘法.所以僅需7次遞歸調用.T (n) =7T (n/2)+Θ(n2)Master 方法:logba=log27, case 1:ε＝

13、log27-2.5T (n)= Θ(nlog7) =Θ(n2.81),例14-3 Strassen算法,7個n/2階矩陣:P1,…,P7 7次n/2階矩陣乘法.8次(n/2)階矩陣加/減法,Strassen Algorithm,void matmul(int *A, int *B, int *R, int n) { if (n == 1) {(*R) += (*A) * (*B); } else {matmul(A

14、, B, R, n/4);matmul(A, B+(n/4), R+(n/4), n/4);matmul(A+2*(n/4), B, R+2*(n/4), n/4);matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4);matmul(A+(n/4), B+2*(n/4), R, n/4);matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4);matmul

15、(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4);matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4); },例14-3,算法展開為一7叉樹,每個節(jié)點有7個子節(jié)點:P1,…P7每個內節(jié)點上只做加減法當分解子問題到n＝1時,在葉節(jié)點處做乘法得到P1,…P7 ;Best to date (of theoretical interest only): Θ(n2.37

16、6)(Don Coppersmith, Shmuel Winograd, Matrix Multiplication via Arithmetic Progressions, STOC 1987: 1-6).,14.2應用,殘缺棋盤 (Defective Chessboard)歸并排序(Merge Sort)快速排序(Quick Sort)選擇 (Selection Problem),Defective Chessboard,De

17、fective Chessboard,Defective Chessboard,殘缺棋盤的問題要求用三格板（t r i o m i n o e s）覆蓋殘缺棋盤。在此覆蓋中，兩個三格板不能重疊，三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格,復雜性分析,n=4k需(n-1)/3個3-方塊填滿棋盤算法的時間復雜度:t(n)=4t(n/4)+c, logba=1,case 1:ε=1t(n)=Θ(n),,,,14.2.2 歸并排序

18、,我們采用平衡分割法來分割n 個元素,即將n 個元素分為A和B 兩個集合,其中A集合中含有n/k 個元素,B中包含其余的元素.然后遞歸地使用分治法對A和B進行排序.當A或B內元素數(shù)<k時使用插入排序.然后采用一個稱為歸并（merge）的過程，將已排好序的A和B合并成一個集合.,例14.5,考慮8個元素,值分別為[10,4,6,3,8,2,5,7 ]。k=2時排序;A1=[10,4, 6, 3] A2=[8,2,5,7]

19、A11=[10,4] A12=[6, 3] A21=[8,2] A22=[5,7]A111=[10] A112=[4] A121=[6] A122=[3] A211=[8] A212=[2] A221=[5] A222=[7]k=4時排序,圖14-6 分治排序算法的偽代碼,算法復雜度,當n/k≈n-(n/k) 時t (n) 的值最小(balance 原理)因此,當k=2時,分治法通常具有最佳性能:當k>2時遞歸展開的深度lo

20、gan, a=k/(k-1),超過log2n.,算法復雜度（續(xù)1）,當k=2時 ,可得到如下遞推公式：,14.2.3 快速排序,分治法還可以用于實現(xiàn)另一種完全不同的排序方法:快速排序(quick sort).在這種方法中,n 個元素被分成三段:左段left，右段right和中段middle.中段僅包含一個元素;左段中各元素都小于等于中段元素;右段中各元素都大于等于中段元素.因此left和right中的元素可以獨立排序,并且不必

21、對left和right的排序結果進行合并.middle中的元素被稱為支點(pivot ).,圖14-9 快速排序的偽代碼,/ /使用快速排序方法對a[ 0 :n- 1 ]排序從a[0 :n- 1]中選擇一個元素作為middle，該元素為支點把余下的元素分割為兩段left 和r i g h t，使得left中的元素都小于等于支點，而right 中的元素都大于等于支點遞歸地使用快速排序方法對left 進行排序遞歸地使用快速排序方法

22、對right 進行排序所得結果為left + middle + right,程序14-6 快速排序,templatevoid QuickSort(T *a, int n){// Sort a[0:n-1] using quick sort. // Requires a[n] must have largest key. quickSort(a, 0, n-1);}templatevoid quickSort(T a[

23、], int l, int r){// Sort a[l:r], a[r+1] has large value. if (l >= r) return; int i = l, // left-to-right cursor j = r + 1; // right-to-left cursor T pivot = a[l];,,程序14-6 快速排序（續(xù)1）,// swap elemen

24、ts >= pivot on left side // with elements = element on left side i = i + 1; } while (a[i] pivot); if (i >= j) break; // swap pair not found Swap(a[i], a[j]); },// place pivot

25、 a[l] = a[j]; a[j] = pivot; quickSort(a, l, j-1); // sort left segment quickSort(a, j+1, r); // sort right segment},,,,分劃用的比較次數(shù),當關鍵字彼此不同時,例如,1,2,…,n,永遠有: j=i-1.這是因為:分劃結束時j指向左邊區(qū)間的右端點(a[j]pivot).所以共進行i-l +r

26、-j+1 =r-l+2次比較.第一遍分劃進行n+1次比較.,算法的時間復雜度,程序quickSort需要的遞歸?？臻g為O(n).如使用堆棧將遞歸化為迭代并每次分劃后將長度較大的段壓入棧中則?？臻g長度為 O(logn). (作業(yè), 習題13)在最壞情況下left總是為空,快速排序所需的計算時間為Θ(n2).在最好情況下,left和right中的元素數(shù)目大致相同,快速排序的復雜性為Θ(nlog2n).但快速排序的平均復雜性也是Θ(

27、nlog2n).,Worst case analysis,Input sorted or reverse sorted.Partition around min or max element.One side of partition always has no elements.,(arithmetic series),Worst case analysis-recursion tree,,cn,Q(1),c(n–1),T(n)

28、= T(0) + T(n–1) + cn,,,Q(1),c(n–2),,,Q(1),Q(1),,,,,T(n)= Q(n) + Q(n2)= Q(n2),Best case analysis,如果分劃點總是在中間: T(n)=2T(n/2)+Θ(n) =Θ(n lg n) 然而分劃在 1/10:9/10,我們也有Θ(n lg n): T(n)=T(n/10)+T(9n/1

29、0)+Θ(n) 運氣也很好!分劃點碰上好運氣的概率很大.所以快速排序平均情形性能很好!,Best case-recursion tree,Q(1),Q(1),,,,,,,,…,…,,,,,…,O(n) leaves,,,,,,Q(n lg n)Lucky!,Average case analysis,假定關鍵字彼此不同則平均關鍵字比較次數(shù),假定Pivot出現(xiàn)在序列中的位置是等可能的,平均情形分析,,,,,,,,,,,,,,,,

30、,,圖14-10 各種排序算法的比較,圖14-12 各排序算法平均時間的曲線圖,14.2.4 選擇問題,定義：對于給定的n個元素的數(shù)組a[0:n-1]，要求從中找出第k小的元素。選擇問題可在O(nlogn)時間內解決，方法是首先對這n個元素進行排序(如使用堆排序或歸并排序），然后取出a[k - 1]中的元素。若使用快速排序，可以獲得更好的平均性能。盡管該算法有一個比較差的漸近復雜性O(n2)。,程序14-7 尋找第k 個元素,temp

31、lateT Select(T a[], int n, int k){// Return k'th smallest element in a[0:n-1]. // Assume a[n] is a dummy largest element. if (k n) throw OutOfBounds(); return select(a, 0, n-1, k);}templateT select(T a[]

32、, int l, int r, int k){// Return k'th smallest in a[l:r]. if (l >= r) return a[l]; int i = l, // left to right cursor j = r + 1; // right to left cursor T pivot = a[l];,,程序14-7 尋找第k 個元素（續(xù)1）,

33、// swap elements >= pivot on left side // with elements = element on left side i = i + 1; } while (a[i] pivot); if (i >= j) break; // swap pair not found Swap(a[i], a[j]); },

34、if (j - l + 1 == k) return pivot; // place pivot a[l] = a[j]; a[j] = pivot; // recursive call on one segment if (j - l + 1 < k) return select(a, j+1, r, k-j+l-1); else return select(a, l, j

35、-1, k);},,,,程序14-7復雜度分析,程序Select在最壞情況下的復雜性是Θ(n2)，如果left 和right總是同樣大小或者相差不超過一個元素，那么可以得到以下遞歸表式：如果n 是2的冪，則通過使用迭代方法，可以得到t (n) = Θ(n) 。提示我們:選擇較好的分點可得到較好的性能,中間的中間規(guī)則,若仔細地選擇支點元素，則最壞情況下的時間開銷也可以變成Θ(n) 。一種選擇支點元素的方法是使用“中間的中間

36、（median-of-median）”規(guī)則：首先將數(shù)組a中的n 個元素分成n/r 組，r 為某一整常數(shù)，除了最后一組外，每組都有r 個元素。然后通過在每組中對r 個元素進行排序來尋找每組中位于中間位置的元素。最后對所得到的n/r 個中間元素，遞歸使用選擇算法，求得”中間之中間”作為支點元素。,例14-6 [中間的中間],考察如下情形：r=5, n=27, 并且a=[2，6，8，1，4，10，20，6，22，11，9，8，4，3，7，8，

37、16，11，10，8，2，14，15，1，12，5，4 ]。 說明： 這27個元素可以被分為6組，每組的中間元素分別為4 , 11 , 7 , 1 0 , 1 2和4，這些中間元素的中間元素為7，將其取為支點元素。,定理14-2,當按“中間的中間”規(guī)則選取支點元素時，以下結論為真：若r=5，且a 中所有元素都不同，那么當n≥24時，有max{| left |, | right | }≤3n/ 4：有 多個中間元素小于mm

38、；不小于mm元素的數(shù)目有上界,,,,r=5 的復雜度,r=5用歸納法可證明當n≥24時有t(n)≤20cn,r=9 的復雜度,當r=9, 那么當n≥90時，有 max{ |left|,|right|}≤7n/8用于尋找第k個元素的時間t (n)可按如下遞歸公式來計算：在上述遞歸公式中，假設當n＜90時使用任意的求解算法，當n≥90時，采用“中間的中間”規(guī)則用分治法求解。利用歸納法可以證明，當n≥90時有t (n)≤

39、72cn。,14.4 復雜性的下限,如果求解一個問題所有算法的復雜性均為W (f (n)) 時，則稱f (n)為該問題的復雜性的下限（lower bound）為了確定一個問題的復雜性下限g (n)，必須證明該問題的每一個求解算法的復雜性均為W (g (n) )。要得到這樣一個結論相當困難，因為不可能考察所有的求解算法。對于大多數(shù)問題，可以建立一個基于輸入和/或輸出數(shù)目的簡單下限。,比較算法,所謂比較算法是指算法的操作主要限于元素比較

40、和元素移動。本節(jié)將建立本章所介紹的兩個分治法求解的問題的確切下限——尋找n 個元素中的最大值和最小值問題以及排序。對于這兩個問題，僅考察基于關鍵字比較的算法。,14.4.1 最小最大問題的下限,程序14-1為按分治法設計的在n 個元素中找最大值與最小值的算法，該算法需做 次元素比較。以下證明：解決該問題的任何一個基于比較的算法，至少需要做 次。問題下界指解決該問題的所有算法的最壞

41、情形復雜度的最小值(min-max): max對所有實例; min對所有算法.,,,,,狀態(tài)空間方法,狀態(tài)空間方法( state space method)。該方法要求首先定義算法的三種狀態(tài)：起始狀態(tài)、中間狀態(tài)和完成狀態(tài)，并需描述每次比較狀態(tài)如何轉換，然后確定從起始狀態(tài)到完成狀態(tài)worst case至少需要的狀態(tài)轉換數(shù)。構造一個產(chǎn)生最壞情形的輸入,我們稱之為敵手(adversary)假設n 個元素互不相同。,Max-min問題的狀

42、態(tài)空間,算法狀態(tài)可用元組(a, b, c, d)來描述，a 表示算法需考察的候選的最大和最小元素的個數(shù)(尚未參加過比較的那些元素) b 表示不再做為最小候選但仍作為最大候選的元素個數(shù)(只勝未敗) c 是不再做為最大候選但仍做為最小候選的元素個數(shù)(只敗未勝)d 是被確定為即非最大也非最小的元素個數(shù)。A，B，C，D代表上述各種元素的集合。,證明（過程）,算法啟動時：起始狀態(tài)為(n,0,0,0)算法結束時：完成狀態(tài)為(0,1,1,

43、n-2)在比較元素的過程中算法狀態(tài)發(fā)生變化當A中的兩個元素比較時，較小的元素放入C，較大的元素放入B(根據(jù)假設所有元素都不相同，因此不會出現(xiàn)相等的情形),引起下面狀態(tài)轉換： (a,b,c,d )→(a-2,b+1,c+1,d),證明（過程續(xù)1）,其他可能的狀態(tài)轉換如下：B中元素比較之后，狀態(tài)轉換為： (a, b, c, d)→(a, b-1, c, d+1 ) C中元素比較之后，狀態(tài)轉換為： (a,

44、b, c, d)→(a, b, c-1, d+ 1 )B與C中元素比較： (a,b,c,d) →(a,b-1,c-1,d+2) *(a,b,c,d) →(1,b,c-1,d+1) （*代表最壞情形狀態(tài)變換）,,A中元素與B中元素進行比較，狀態(tài)轉換為： (a, b, c, d)→(a-1, b, c, d+1) (A中元素>B中元素) * (a, b, c, d)→(a-1, b, c+1,

45、d) (A中元素C中元素),證明（過程續(xù)2）,A與D中元素比較狀態(tài)轉換: (a,b,c,d)->(a-1,b+1,c,d) (a,b,c,d)->(a-1,b,c+1,d)因我們分析最壞情形復雜度的下界，所以A與B或C中元素比較時應考慮最壞情形： (a,b,c,d)－>(a-1,b,c+1,d) (a,b,c,d)－>(a-1,b+1,c,d)構造敵手(adversary):當A中元素

46、x與B中元素y比較時,如 x>y則不會發(fā)生上述狀態(tài)轉換.因y從未輸過,重新取y的值使 y>x.新的y不會影響以前的比賽的結果.B與C的元素比較令B的元素勝.,,其他比較無實質意義(構造敵手),例如D中元素x與B中元素y比較且x>y,則改變y得值使其大于x,不會影響以前的結果.無狀態(tài)轉換發(fā)生.D與C中元素比較同樣處理.敵手構造的輸入使得從初始狀態(tài)到結束狀態(tài)至少要做的狀態(tài)轉數(shù):d從0增至n-2,至少要n－2次比較，而且

47、這些比較不會引起a減少(只能B中或C中元素自己比);a從n減至0，至少要做：當n=2m(為偶數(shù))時為m次；當n=2m+1時為m+1次；所以至少要做[3n/2]-2次比較,證明（總結）,任何求最大最小的算法從起始狀態(tài)到完成狀態(tài)所用比較次數(shù)不可少于 所有基于比較的求最大最小算法所需比較次數(shù)的下界是程序14-1是解決最大最小問題的最優(yōu)算法,14.4.2 排序算法的下限,可用決策樹（decision-tree）來證明下限。證明過程中用樹

48、來模擬算法的執(zhí)行過程。對于樹的每個內部節(jié)點，算法執(zhí)行一次比較并根據(jù)比較結果移向它的某一子節(jié)點。算法在葉節(jié)點處終止。,圖14-19 n=3 時InsertionSort 的決策樹,對圖14-19證明過程 的說明,圖14-19給出了對三個元素a [0 : 2]使用InsertionSort（見程序2-15）排序時的決策樹。每個內部節(jié)點有一個i : j的標志，表示a[i]與a[j]進行比較。如果a[i]＜a[j]，算法移向左孩子；如果a[i]

49、＞a[j]，移向右孩子。因為元素互不相同，所以a[i]=a[j]不會發(fā)生。葉節(jié)點標出了所產(chǎn)生的排序。圖14-19中最左路徑代表： a[1]＜a[0]，a[2]＜a[0]，a[2]＜a[1]，因此最左葉節(jié)點為(a[2], a[1], a[0])。,決策樹說明,決策樹中每個葉節(jié)點代表一種輸入排列的排序結果。正確的排序算法對于n！個輸入必須產(chǎn)生n！個可能的排列，因此決策樹中至少要有n！個葉節(jié)點。有n個葉節(jié)點的二叉樹的高度至少為logn因此