1、分治算法(Divide & Conquer Algorithm),宫秀军天津大学计算机科学与技术学院,提纲,分治法基本原理应用归并排序快速排序选择问题复杂性的下限最大最小问题的下限排序算法的下限,14.1 分治法思想,分治法设计算法的思想将问题分成(divide)多个子问题；递归地(conquer)解决每个子问题；将子问题的解合并(combine)成原问题的解。分治法常常得到递归算法Merge-Sort, Quick SortDiscrete Fourier transform (FFT). 算法复杂性分析Master methodSubstitution method,例14-1 找出伪币,
2、现有16个硬币,其中有一个是伪币，并且伪币重量比真币轻。试用一台天平找出这枚伪币。两两比较,最坏情形需8次比较找出伪币。分治法仅需4次比较找出伪币。,Compute an,Problem: Compute an, where nN.Naive algorithm: (n).Divide-and-conquer algorithm:an= an/2an/2 if n is even;an =a(n1)/2a(n1)/2a if n is odd.ComplexityT(n)=T(n/2)+(1)Master方法, a=1 b=2 Case 2: logba=0,k0T(n)=(lgn),例14-
3、2 金块问题,问题有若干金块试用一台天平找出其中最轻和最重的金块.等价于n个数中找出最大和最小的数.直接求解1：先找出最大值,然后在剩下的n-1个数中再找出最小值.需2n-3次比较.,例14-2,直接求解2：最大最小值同时进行查找,func minmax( T a, n, T For i1 to n-1 do if aimax maxai,当输入数组为顺序时,算法要做2(n-1)次比较当输入数组为逆序时,算法要做n-1次比较,例14-2,分治法求解,int minmax-dc(T A0,n-1, T else mn/2 minmax-dc (A0,m-1,max1,min1), minmax-
4、dc (Am,n-1,max2,min2), maxmax(max1,max2), minmin(min1,min2), return.,例14-2 （解续）,设c(n)为使用分治法所需要的比较次数,假设n=2k则有: c(n)=1 ,n = 2 ; 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为奇数时,n=2m+1,比较m对相邻元素, 比较次数
5、为3*m=3*(n-1)/2 =3n/2-3/2=3n/2-1/2-3/2 =3n/2-2 表示向上取整.当n为偶数时,n=2m,比较m-1对相邻元素 比较次数为1+3*(m-1)=1+3*(n-2)/2 =1+3n/2-3 =3n/2-2该算法所用比较次数最少,例14-3 矩阵乘法,两个nn 阶的矩阵A与B的乘积是另一个nn 阶矩阵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; in; i+) for (int j=0; jn; j+) T
6、sum=0; for (int k=0; kn; k+) sum+=Aik*Bkj cij=sum; ,假如每一个C(i, j)都用此公式计算,则计算C 所需要的运算次数为n3次乘法和n2(n-1)次加法.,矩阵乘法-分治法,22分块矩阵乘法,a,b,c,d,是A的4个(n/2)阶子矩阵,e,f,g,h是B的4个(n/2)阶子矩阵,矩阵乘法-分治法,基本观点：nn matrix = 22 matrix of (n/2)(n/2) submatrices,8 mults of (n/2)(n/2) submatrices,4 adds of (n/2)(n/2) submatrices,recu
7、rsive,复杂性分析T(n)=8T(n/2)+(n2) （(n2)4个(n/2)阶矩阵加法的计算时间）nloga=nlog8=n3 CASE 1T(n)=(n3),从分治法没得到好处！,算法,基本观点合并分块矩阵以减少乘法次数22 矩阵相乘可用7次乘法.所以仅需7次递归调用.T (n) =7T (n/2)+(n2)Master 方法:logba=log27, case 1: log27-2.5T (n)= (nlog7) =(n2.81),例14-3 Strassen算法,7个n/2阶矩阵:P1,P7 7次n/2阶矩阵乘法.8次(n/2)阶矩阵加/减法,Strassen Algorithm,
8、void matmul(int *A, int *B, int *R, int n) if (n = 1) (*R) += (*A) * (*B); else matmul(A, 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(A+3
9、*(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叉树,每个节点有7个子节点:P1,P7每个内节点上只做加减法当分解子问题到n1时,在叶节点处做乘法得到P1,P7 ;Best to date (of theoretical interest only): (n2.376)(Don Coppersmith, Shmuel Winograd, Matrix Multiplication via Arithmetic Progressions, STOC 198
10、7: 1-6).,14.2应用,残缺棋盘 (Defective Chessboard)归并排序(Merge Sort)快速排序(Quick Sort)选择 (Selection Problem),Defective Chessboard,Defective 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
11、=1,case 1:=1t(n)=(n),14.2.2 归并排序,我们采用平衡分割法来分割n 个元素,即将n 个元素分为A和B 两个集合,其中A集合中含有n/k 个元素,B中包含其余的元素.然后递归地使用分治法对A和B进行排序.当A或B内元素数2时递归展开的深度logan, a=k/(k-1),超过log2n.,算法复杂度（续1）,当k=2时 ,可得到如下递推公式：,14.2.3 快速排序,分治法还可以用于实现另一种完全不同的排序方法:快速排序(quick sort).在这种方法中,n 个元素被分成三段:左段left，右段right和中段middle.中段仅包含一个元素;左段中各元素都小于等于
12、中段元素;右段中各元素都大于等于中段元素.因此left和right中的元素可以独立排序,并且不必对left和right的排序结果进行合并.middle中的元素被称为支点(pivot ).,图14-9 快速排序的伪代码,/ /使用快速排序方法对a 0 :n- 1 排序从a0 :n- 1中选择一个元素作为middle，该元素为支点把余下的元素分割为两段left 和r i g h t，使得left中的元素都小于等于支点，而right 中的元素都大于等于支点递归地使用快速排序方法对left 进行排序递归地使用快速排序方法对right 进行排序所得结果为left + middle + right,程序1
13、4-6 快速排序,templatevoid QuickSort(T *a, int n)/ Sort a0:n-1 using quick sort. / Requires an must have largest key. quickSort(a, 0, n-1);templatevoid quickSort(T a, int l, int r)/ Sort al:r, ar+1 has large value. if (l = r) return; int i = l, / left-to-right cursor j = r + 1; / right-to-left cursor T p
14、ivot = al;,程序14-6 快速排序（续1）,/ swap elements = pivot on left side / with elements = element on left side i = i + 1; while (ai pivot); if (i = j) break; / swap pair not found Swap(ai, aj); ,/ place pivot al = aj; aj = pivot; quickSort(a, l, j-1); / sort left segment quickSort(a, j+1, r); / sort right s
15、egment,分划用的比较次数,当关键字彼此不同时,例如,1,2,n,永远有: j=i-1.这是因为:分划结束时j指向左边区间的右端点(ajpivot).所以共进行i-l +r-j+1 =r-l+2次比较.第一遍分划进行n+1次比较.,算法的时间复杂度,程序quickSort需要的递归栈空间为O(n).如使用堆栈将递归化为迭代并每次分划后将长度较大的段压入栈中则栈空间长度为 O(logn). (作业, 习题13)在最坏情况下left总是为空,快速排序所需的计算时间为(n2).在最好情况下,left和right中的元素数目大致相同,快速排序的复杂性为(nlog2n).但快速排序的平均复杂性也是(
16、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(n1),T(n) = T(0) + T(n1) + cn,Q(1),c(n2),Q(1),Q(1),T(n)= Q(n) + Q(n2)= Q(n2),Best case analysi
17、s,如果分划点总是在中间: T(n)=2T(n/2)+(n) =(n lg n) 然而分划在 1/10:9/10,我们也有(n lg n): T(n)=T(n/10)+T(9n/10)+(n) 运气也很好!分划点碰上好运气的概率很大.所以快速排序平均情形性能很好!,Best case-recursion tree,Q(1),Q(1),O(n) leaves,Q(n lg n)Lucky!,Average case analysis,假定关键字彼此不同则平均关键字比较次数,假定Pivot出现在序列中的位置是等可能的,平均情形分析,图14-10 各种排序算法的比较,图14-12 各排序算法平均时间
18、的曲线图,14.2.4 选择问题,定义：对于给定的n个元素的数组a0:n-1，要求从中找出第k小的元素。选择问题可在O(nlogn)时间内解决，方法是首先对这n个元素进行排序(如使用堆排序或归并排序），然后取出ak - 1中的元素。若使用快速排序，可以获得更好的平均性能。尽管该算法有一个比较差的渐近复杂性O(n2)。,程序14-7 寻找第k 个元素,templateT Select(T a, int n, int k)/ Return kth smallest element in a0:n-1. / Assume an is a dummy largest element. if (k n)
19、 throw OutOfBounds(); return select(a, 0, n-1, k);templateT select(T a, int l, int r, int k)/ Return kth smallest in al:r. if (l = r) return al; int i = l, / left to right cursor j = r + 1; / right to left cursor T pivot = al;,程序14-7 寻找第k 个元素（续1）,/ swap elements = pivot on left side / with elements
20、= element on left side i = i + 1; while (ai pivot); if (i = j) break; / swap pair not found Swap(ai, aj); ,if (j - l + 1 = k) return pivot; / place pivot al = aj; aj = pivot; / recursive call on one segment if (j - l + 1 B中元素) * (a, b, c, d)(a-1, b, c+1, d) (A中元素C中元素),证明（过程续2）,A与D中元素比较状态转换: (a,b,c,d
21、)-(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中元素x与B中元素y比较时,如 xy则不会发生上述状态转换.因y从未输过,重新取y的值使 yx.新的y不会影响以前的比赛的结果.B与C的元素比较令B的元素胜.,其他比较无实质意义(构造敌手),例如D中元素x与B中元素y比较且xy,则改变y得值使其大于x,不会影响以前的结果.无状态转换发生.D与C中元素比较同样处理.敌手
22、构造的输入使得从初始状态到结束状态至少要做的状态转数:d从0增至n-2,至少要n2次比较，而且这些比较不会引起a减少(只能B中或C中元素自己比);a从n减至0，至少要做：当n=2m(为偶数)时为m次；当n=2m+1时为m+1次；所以至少要做3n/2-2次比较,证明（总结）,任何求最大最小的算法从起始状态到完成状态所用比较次数不可少于 所有基于比较的求最大最小算法所需比较次数的下界是程序14-1是解决最大最小问题的最优算法,14.4.2 排序算法的下限,可用决策树（decision-tree）来证明下限。证明过程中用树来模拟算法的执行过程。对于树的每个内部节点，算法执行一次比较并根据比较结果移向
23、它的某一子节点。算法在叶节点处终止。,图14-19 n=3 时InsertionSort 的决策树,对图14-19证明过程 的说明,图14-19给出了对三个元素a 0 : 2使用InsertionSort（见程序2-15）排序时的决策树。每个内部节点有一个i : j的标志，表示ai与aj进行比较。如果aiaj，算法移向左孩子；如果aiaj，移向右孩子。因为元素互不相同，所以ai=aj不会发生。叶节点标出了所产生的排序。图14-19中最左路径代表： a1a0，a2a0，a2a1，因此最左叶节点为(a2, a1, a0)。,决策树说明,决策树中每个叶节点代表一种输入排列的排序结果。正确的排序算法对于n！个输入必须产生n！个可能的排列，因此决策树中至少要有n！个叶节点。有n个叶节点的二叉树的高度至少为logn因此决策树的高度至少为nlogn每一个比较排序算法在最坏情况下至少要进行W(nlogn)次比较。每个有n！个叶节点的决策树的平均外路长度为W(nlogn)；所以每个比较排序算法的平均复杂性也是W(nlogn)。,结论,由前面的证明可以看出，堆排序、归并排序在最坏情况下有较好的性能（针对渐进复杂性而言），堆排序、归并排序、快速排序在平均情况下性能较优。,
