分治算法（divide & conquer algorithm）

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

2、常得到遞歸算法Merge-Sort, Quick SortDiscrete Fourier transform (FFT). 算法復(fù)雜性分析Master methodSubstitution method,例14-1 [找出偽幣],現(xiàn)有16個(gè)硬幣,其中有一個(gè)是偽幣，并且偽幣重量比真幣輕。試用一臺(tái)天平找出這枚偽幣。兩兩比較,最壞情形需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 [金塊問題],問題有若干金塊試用一臺(tái)天平找出其中最輕和最重的金塊.等價(jià)于n個(gè)數(shù)中找出最大和最小的數(shù).直接求解1：先找出最大值,然后在剩下的n-1個(gè)數(shù)中再找出最小值.需2n-3次比較.,例14-2,直接求解2：最大最小值同時(shí)進(jìn)行查找,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]},當(dāng)輸入數(shù)組為順序時(shí),算法要做2(n-1)次比較當(dāng)輸入數(shù)組為逆序時(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ù)）,設(shè)c(n)為使用分治法所需要的比較次數(shù),假設(shè)n=2k則有: c(n)=1 ,n = 2 ;

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

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

9、n/2]-2該算法所用比較次數(shù)最少,例14-3 [矩陣乘法],兩個(gè)n×n 階的矩陣A與B的乘積是另一個(gè)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; }},假如每一個(gè)C(i, j)都用此公式計(jì)算,則計(jì)算C 所需要的運(yùn)算次數(shù)為n3次乘法和n2(n-1)次加法.,矩陣乘法-分治法

11、,2×2分塊矩陣乘法,a,b,c,d,是A的4個(gè)(n/2)階子矩陣,e,f,g,h是B的4個(gè)(n/2)階子矩陣,矩陣乘法-分治法,基本觀點(diǎn)：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,,復(fù)雜性分析T(n)=8T(n/2)+Θ(n2) （Θ(n2)－4個(gè)(n/2)階矩陣加法的計(jì)算時(shí)間）nloga=nlog8=n3 ? CASE 1?T(n)=Θ(n3),從分治法沒得到好處！,算法,基本觀點(diǎn)合并分塊矩陣以減少乘法次數(shù)2×2 矩陣相乘可用7次乘法.所以僅需7次遞歸調(diào)用.T (n) =7T (n/2)+Θ(n2)Master 方法:logba=log27, case 1:ε＝

13、log27-2.5T (n)= Θ(nlog7) =Θ(n2.81),例14-3 Strassen算法,7個(gè)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叉樹,每個(gè)節(jié)點(diǎn)有7個(gè)子節(jié)點(diǎn):P1,…P7每個(gè)內(nèi)節(jié)點(diǎn)上只做加減法當(dāng)分解子問題到n＝1時(shí),在葉節(jié)點(diǎn)處做乘法得到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應(yīng)用,殘缺棋盤 (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）覆蓋殘缺棋盤。在此覆蓋中，兩個(gè)三格板不能重疊，三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格,復(fù)雜性分析,n=4k需(n-1)/3個(gè)3-方塊填滿棋盤算法的時(shí)間復(fù)雜度:t(n)=4t(n/4)+c, logba=1,case 1:ε=1t(n)=Θ(n),,,,14.2.2 歸并排序

18、,我們采用平衡分割法來分割n 個(gè)元素,即將n 個(gè)元素分為A和B 兩個(gè)集合,其中A集合中含有n/k 個(gè)元素,B中包含其余的元素.然后遞歸地使用分治法對(duì)A和B進(jìn)行排序.當(dāng)A或B內(nèi)元素?cái)?shù)<k時(shí)使用插入排序.然后采用一個(gè)稱為歸并（merge）的過程，將已排好序的A和B合并成一個(gè)集合.,例14.5,考慮8個(gè)元素,值分別為[10,4,6,3,8,2,5,7 ]。k=2時(shí)排序;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時(shí)排序,圖14-6 分治排序算法的偽代碼,算法復(fù)雜度,當(dāng)n/k≈n-(n/k) 時(shí)t (n) 的值最小(balance 原理)因此,當(dāng)k=2時(shí),分治法通常具有最佳性能:當(dāng)k>2時(shí)遞歸展開的深度lo

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

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

22、對(duì)right 進(jìn)行排序所得結(jié)果為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ù),當(dāng)關(guān)鍵字彼此不同時(shí),例如,1,2,…,n,永遠(yuǎn)有: j=i-1.這是因?yàn)?分劃結(jié)束時(shí)j指向左邊區(qū)間的右端點(diǎn)(a[j]pivot).所以共進(jìn)行i-l +r

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

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,如果分劃點(diǎn)總是在中間: 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) 運(yùn)氣也很好!分劃點(diǎn)碰上好運(yùn)氣的概率很大.所以快速排序平均情形性能很好!,Best case-recursion tree,Q(1),Q(1),,,,,,,,…,…,,,,,…,O(n) leaves,,,,,,Q(n lg n)Lucky!,Average case analysis,假定關(guān)鍵字彼此不同則平均關(guān)鍵字比較次數(shù),假定Pivot出現(xiàn)在序列中的位置是等可能的,平均情形分析,,,,,,,,,,,,,,,,

30、,,圖14-10 各種排序算法的比較,圖14-12 各排序算法平均時(shí)間的曲線圖,14.2.4 選擇問題,定義：對(duì)于給定的n個(gè)元素的數(shù)組a[0:n-1]，要求從中找出第k小的元素。選擇問題可在O(nlogn)時(shí)間內(nèi)解決，方法是首先對(duì)這n個(gè)元素進(jìn)行排序(如使用堆排序或歸并排序），然后取出a[k - 1]中的元素。若使用快速排序，可以獲得更好的平均性能。盡管該算法有一個(gè)比較差的漸近復(fù)雜性O(shè)(n2)。,程序14-7 尋找第k 個(gè)元素,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 個(gè)元素（續(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復(fù)雜度分析,程序Select在最壞情況下的復(fù)雜性是Θ(n2)，如果left 和right總是同樣大小或者相差不超過一個(gè)元素，那么可以得到以下遞歸表式：如果n 是2的冪，則通過使用迭代方法，可以得到t (n) = Θ(n) 。提示我們:選擇較好的分點(diǎn)可得到較好的性能,中間的中間規(guī)則,若仔細(xì)地選擇支點(diǎn)元素，則最壞情況下的時(shí)間開銷也可以變成Θ(n) 。一種選擇支點(diǎn)元素的方法是使用“中間的中間

36、（median-of-median）”規(guī)則：首先將數(shù)組a中的n 個(gè)元素分成n/r 組，r 為某一整常數(shù)，除了最后一組外，每組都有r 個(gè)元素。然后通過在每組中對(duì)r 個(gè)元素進(jìn)行排序來尋找每組中位于中間位置的元素。最后對(duì)所得到的n/r 個(gè)中間元素，遞歸使用選擇算法，求得”中間之中間”作為支點(diǎn)元素。,例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個(gè)元素可以被分為6組，每組的中間元素分別為4 , 11 , 7 , 1 0 , 1 2和4，這些中間元素的中間元素為7，將其取為支點(diǎn)元素。,定理14-2,當(dāng)按“中間的中間”規(guī)則選取支點(diǎn)元素時(shí)，以下結(jié)論為真：若r=5，且a 中所有元素都不同，那么當(dāng)n≥24時(shí)，有max{| left |, | right | }≤3n/ 4：有 多個(gè)中間元素小于mm

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

39、72cn。,14.4 復(fù)雜性的下限,如果求解一個(gè)問題所有算法的復(fù)雜性均為W (f (n)) 時(shí)，則稱f (n)為該問題的復(fù)雜性的下限（lower bound）為了確定一個(gè)問題的復(fù)雜性下限g (n)，必須證明該問題的每一個(gè)求解算法的復(fù)雜性均為W (g (n) )。要得到這樣一個(gè)結(jié)論相當(dāng)困難，因?yàn)椴豢赡芸疾焖械那蠼馑惴?。?duì)于大多數(shù)問題，可以建立一個(gè)基于輸入和/或輸出數(shù)目的簡單下限。,比較算法,所謂比較算法是指算法的操作主要限于元素比較

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

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

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

43、n-2)在比較元素的過程中算法狀態(tài)發(fā)生變化當(dāng)A中的兩個(gè)元素比較時(shí)，較小的元素放入C，較大的元素放入B(根據(jù)假設(shè)所有元素都不相同，因此不會(huì)出現(xiàn)相等的情形),引起下面狀態(tài)轉(zhuǎn)換： (a,b,c,d )→(a-2,b+1,c+1,d),證明（過程續(xù)1）,其他可能的狀態(tài)轉(zhuǎn)換如下：B中元素比較之后，狀態(tài)轉(zhuǎn)換為： (a, b, c, d)→(a, b-1, c, d+1 ) C中元素比較之后，狀態(tài)轉(zhuǎn)換為： (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中元素進(jìn)行比較，狀態(tài)轉(zhuǎn)換為： (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)轉(zhuǎn)換: (a,b,c,d)->(a-1,b+1,c,d) (a,b,c,d)->(a-1,b,c+1,d)因我們分析最壞情形復(fù)雜度的下界，所以A與B或C中元素比較時(shí)應(yīng)考慮最壞情形： (a,b,c,d)－>(a-1,b,c+1,d) (a,b,c,d)－>(a-1,b+1,c,d)構(gòu)造敵手(adversary):當(dāng)A中元素

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

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

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

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