算法设计与分析第3讲 分治法

3.1分治法的基本思想 分治法的基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。——孙子兵法3.１分治法的基本思想 分治法的基本步骤 divide-and-conquer(P){　if(|P|<=n0)adhoc(P);//解决小规模的问题　dividePintosmallersubinstancesP1,P2,...,Pa；//分解问题　for(i=1,i<=a,i++)　yi=divide-and-conquer(Pi);//递归的解各子问题　returnmerge(y1,...,ya);//将各子问题的解合并为原问题的解}人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。3.１分治法的基本步骤 分治法的复杂性分析 一个分治法将规模为n的问题分成a个规模为n／b的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有3.2合并排序 １分为两个半表 ２每个表递归排序 ３合并　（f(n)=θ(n)） T(n)=2T(n/2)+θ(n) 主方法case2,T(n)=θ(n.lgn)3.3二分搜索技术 给定已按升序排好序的n个元素a[1:n]，现要在这n个元素中找出一特定元素x。算法及其复杂性 据此容易设计出二分搜索算法：publicintbinarySearch(int[]a,intx,left,right){//在a[start]<=a[start+1]<=...<=a[stop]中搜索x//找到x时返回其在数组中的位置，否则返回-1if(left==right&&x!=a[left])return-1;intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])returnbinarySearch[a,x,middle,rught];ElsereturnbinarySearch[a,x,left,midle];} 算法复杂度分析：T(n)=T(n/2)+θ(1),case2:θ(logn)。3.4大整数的乘法 设计一个有效的算法，可以进行两个n位大整数的乘法运算 小学的方法：θ(n2)效率太低 分治法: X=a2n/2+b Y=c2n/2+d XY=ac2n+(ad+bc)2n/2+bd 复杂度分析 Case1:T(n)=θ(n2)没有改进算法改进 为了降低时间复杂度，必须减少乘法的次数。为此，我们把XY写成另外的形式： XY=ac2n+((a-b)(d-c)+ac+bd)2n/2+bd或 XY=ac2n+((a+b)(c+d)-ac-bd)2n/2+bd 复杂性： 这两个算式看起来更复杂一些，但它们仅需要3次n/2位乘法[ac、bd和(a±c)(b±d)]，于是 T(n)=θ(nlog3)=θ(n1.59)较大的改进 细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+b,c+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。3.5Strassen矩阵乘法 n×n矩阵A和B的乘积矩阵C中的元素C[i,j]定义为： 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的n*n个元素所需的计算时间为θ(n3)简单分治法求矩阵乘 首先假定n是2的幂。使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为： 由此可得： 复杂度分析 Case1:T(n)=θ(n3)没有改进改进算法 为了降低时间复杂度，必须减少乘法的次数。而其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次。为此，Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法（但增加了加/减法次数）：M1=A11(B12-B22)　M2=(A11+A12)B22M3=(A21+A22)B11　M4=A22(B21-B11)M5=(A11+A22)(B11+B22)　M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12) 做了这7次乘法后，在做若干次加/减法就可以得到：C11=M5+M4-M2+M6　C12=M1+M2C21=M3+M4　C22=M5+M1-M3-M7 复杂度分析 T(n)=θ(nlog7)=θ(n2.81)较大的改进更快的方法 Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。 目前最好的计算时间上界是O(n2.376) 是否能找到θ(n2)的算法？目前为止还没有结果。3.6Fibonacci数列 例2Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为： 第n个Fibonacci数可递归地计算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}　用递归树分析，算法的复杂度是指数ψn,Fibonacci数列 2自底向上，T(n)=θ(n),　 3Gn=(Fn-1Fn*(11 FnFn-1)10 Gn=Xn T(n)=T(n/2)+θ(1) T(n)=θ(lgn)3.7棋盘覆盖 在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 易知，覆盖任意一个2k×2k的特殊棋盘，用到的骨牌数恰好为(4K-1)/3。分治策略求解 当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。算法描述voidCB(inttr,tc,dr,dc,size){ if(size==1)return;intt=tile++;//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格CB(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中CB(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s-1][tc+s]=t;//覆盖其余方格CB(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盘中CB(tr+s,tc,dr,dc,s);else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格CB(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盘中CB(tr+s,tc+s,dr,dc,s);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格CB(tr+s,tc+s,tr+s,tc+s,s);}}复杂度分析 说明： 整形二维数组Board表示棋盘，Borad[0][0]使棋盘的左上角方格。 tile是一个全局整形变量，用来表示L形骨牌的编号，初始值为0。 tr：棋盘左上角方格的行号；tc：棋盘左上角方格的列号； dr：特殊方各所在的行号；dc：特殊方各所在的列号； size：size=2k，棋盘规格为2k×2k。 复杂度分析： T(k)=4k-1=O(4k)渐进意义下的最优算法