分治-第九章算法设计与分析

9.2分治法本节学习的主要内容9.2.1分治法的基本思想9.2.2最大子段和问题9.2.3

Strassen矩阵乘法9.2.4大整数的乘法9.2.5

线性时间选择9.2.1分治法的基本思想分治法的基本思想是将一个规模为n的问题分解为a个规模小的子问题.这些子问题互相独立且与原问题相同,每个子问题的规模为n/b。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法的一般算法设计模式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，y2，…yk);}分治法的设计模式中子算法的描述|P|是问题规模。Adhoc(P)是基本子算法，用于直接解小规模问题。Merge(y1，y2，…ya)是合并子算法，用于将子问题P1,P2,…Pa的解y1，y2，…ya合并为P的解。分治法的分割原则：最好使子问题的规模大致相同。分治法的计算效率前提：考虑将规模为n的问题分成a个规模为n/b的子问题。无妨设n0=1，且Adhoc解规模为1的问题耗费1个单位时间。Merge耗费f(n)个单位时间。T(n)表示Divide-and-Conquer(P)解规模为|P|=n的问题所需计算时间，则有解递归方程T(n)T(n)=aT(n/b)+f(n)aT(n/b)=a2T(n/b2)+af(n/b)a2T(n/b2)=a3T(n/b3)+a2f(n/b2):ajT(n/bj)=aj+1T(n/bj+1)+ajf(n/bj):awT(n/bw)=aw+1T(n/bw+1)+awf(n/bw)其中w+1=logbn递归方程T(n)的解算例:T(n)=3T(n/2)+nT(n)=3T(n/2)+f(n)3T(n/2)=32T(n/22)+3f(n/2)32T(n/22)=33T(n/23)+32f(n/22):3jT(n/2j)=3j+1T(n/2j+1)+3jf(n/2j):3wT(n/2w)=3w+1T(n/2w+1)+3wf(n/2w)其中w+1=log2nT(n)=3T(n/2)+n的解主定理(Mastertheorem)(Mastertheorem)设T(n)由递归式T(n)=aT(n/b)+f(n)对非负整数定义，其中k1,b1,n/b为n/b或n/b,f(n)为一函数，那么T(n)有如下的渐进界：若对于某常数>0，有f(n)=O(n(logba)-)，则T(n)=(n(logba))//f(n)多项式地小于n(logba)若f(n)=(n(logba)),则T(n)=(n(logba).lg(n))//

n(logba)与f(n)同阶若对于某常数>0，有f(n)=(n(logba)+)，且对常数c<1与所有足够大的n，有af(n/b)cf(n)，则T(n)=(f(n))理解Master定理第3条若对于某常数>0，有f(n)=(n(logba)+)，且对常数c<1与所有足够大的n，有af(n/b)cf(n)，则T(n)=(f(n))f(n)多项式地大于于n(logba)“正规性”条件：af(n/b)≤cf(n)。这个附加的“正规性”条件的直观含义是a个子问题的再分解和在综合所需的时间最多与原问题的分解和综合所需的时间同阶。Master定理的应用(一)T(n)=9T(n/3)+n准备：a=9,b=3f(n)=nn(logba)=n(log39)=n2比较：=1,f(n)=n=O(n(log39)-)n(logba)多项式地大于f(n)结论：T(n)=(n(log39))=(n2)Master定理的应用(二)T(n)=T(2n/3)+1准备：a=1,b=3/2f(n)=1n(logba)=n(log3/21)=n0=1比较：f(n)=1=(n(log3/21))结论：T(n)=(n(log3/21).lg(n))=(lg(n))Master定理的应用(三)T(n)=3T(n/4)+nlg(n)准备：a=3,b=4f(n)=nlg(n)n(logba)=n(log43)比较：f(n)=nlg(n)=(n(log43))af(n/b)=3f(n/4)=3(n/4)lg(n/4)3/4nlg(n),c=3/4结论：T(n)=(n.lg(n))=分析分治法时，通常的递归公式我们关心的一般是最坏情况下的计算时间复杂度的上界，所以用=和用<=是没有本质区别的。返回9.2.2最大子段和问题：给定由n个整数(可能为负整数)组成的序列a1，a2，…an，求该序列形如

的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0，所求的最优值为

max{0,}最大子段和的例子当(a1，a2，a3，a4，a5，a6)=(-2,11,-4,13,-5,-2)时，最大段子和为当(a1，a2，a3，a4，a5，a6)=(-2,-11,-4,-3,-5,-2)时，规定最大段子和为01.最大子段和问题的Naïve算法intMaxSum(intn,int*a,int&besti,int&bestj){ intsum=0;//保存数组a的最大子段和,初始为0 for(inti=1;i<=n;i++) for(intj=i;j<=n;j++){ intthissum=0; for(intk=i;k<=j;k++)thissum+=a[k]; if(thissum>sum){ sum=thissum;besti=i;bestj=j; } }returnsum;}//算法有3重循环，其计算时间的上界为O(n3)计算从i开始到j结束的子段和Naïve算法的计算时间和改进算法有3重循环，其计算时间的上界为O(n3)改进策略：考虑所有以i开始的子段计算所有以i开始的子段和公式：最大子段和的例子(a1，a2，a3，a4，a5)=(-2,11,-4,13,-5)以a1开始的最大子段和:(-2),(-2+11),(-2+11-4),(-2+11-4+13),(-2+11-4+13-5)

以a2开始的最大子段和:(11),(11-4),(11-4+13),(11-4+13-5)以a3开始的最大子段和:(-4),(-4+13),(-4+13-5)以a4开始的最大子段和:(13),(13-5)以a5开始的最大子段和:(-5)最大子段和问题的改进算法intMaxSum(intn,int*a,int&besti,int&bestj){ intsum=0;//保存数组a的最大子段和,初始为0 for(inti=1;i<=n;i++){intthissum=0; for(intj=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum){ sum=thissum;besti=i;bestj=j; } }returnsum;}//算法有2重循环，其计算时间的上界为O(n2)该循环计算以i开始的最大子段和2.最大子段和问题的分治算法分治策略：将序列a[1..n]分成长度相等的两段a[1..n/2]和a[n/2+1..n],则a[1..n]的最大子段和有3种可能的情形：a[1..n]的最大子段和与a[1..n/2]的最大子段和相同；a[1..n]的最大子段和与a[n/2+1..n]的最大子段和相同；a[1..n]的最大子段和为,且1in/2,n/2+1jn(最大子段跨越了2个大致相等的子段)对于前面的1和2这两种情况可以用递归的方法求得。对于前面的情况3，容易看出a[n/2]和a[n/2+1]在最大子段中。定理：如果a[1..n]的最大子段和为,且1in/2,n/2+1jn，即最大子段为(ai，ai+1，…aj)，则:

(ai，ai+1，…an/2)为a[1..n/2]的以a[n/2]结尾的最大子段且

(an/2+1，an/2+2，…aj)为a[n/2+1..n]的以a[n/2+1]开始的最大子段。证明:用反证法。如果(ai，ai+1，…an/2)不是a[1..n/2]的以an/2结尾的最大子段且(an/2+1，an/2+2，…aj)不是a[n/2+1..n]中以an/2+1开始的最大子段，则存在另一个子段(ai1，ai1+1，…an/2)是a[1..n/2]的以an/2结尾的最大子段,同时存在另一个子段(an/2+1，an/2+2，…aj1)是a[n/2+1..n]的以an/2+1开始的最大子段，于是于是因此(ai1，ai1+1，…an/2，an/2+1，an/2+2，…aj1)是a[1..n]的最大子段，这与(ai，ai+1，…an/2，an/2+1，an/2+2，…aj)是a[1..n]的最大子段矛盾。对于前面的第3种情况，容易看出a[n/2]和a[n/2+1]在最大子段中。对于前面的第3种情况,先计算a[1..n/2]中的以a[n/2]结尾的最大子段和s1，再计算计算a[n/2+1..n]中的以a[n/2+1]开始的最大子段和s2，s1+s2即为a[1..n]中的最大子段和。对于前面3种情况，分别求出3个最大子段和，然后再求出这3个最大子段和之中的最大者即为为a[1..n]中的最大子段和。最大子段和问题的分治算法的开销a=2,b=2Master定理的应用T(n)=2T(n/2)+n准备：a=2,b=2f(n)=nn(logba)=n(log22)=n1=n比较：f(n)=n=(n(log22))=(n)结论：T(n)=(n(log22).lg(n))=(nlg(n))返回9.2.3Strassen矩阵乘法问题：设A=(aij)nn和B=(bij)nn是2个n乘n的矩阵，它们的乘积C=AB=(cij)nnNaïve的解决方案：按定义计算，每计算一个cij需要做n次乘法和n-1次加法。要计算C中的n2个元素所需时间为O(n3)Strassen矩阵乘法-分治策略假设矩阵的阶n是2的幂。将矩阵A,B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个自矩阵的阶都是n/2。Strassen矩阵乘法-分治策略C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22矩阵乘法的递归定义：n=2，需要8次乘法和4次加法n>2，继续将矩阵分成4块Strassen矩阵乘法-分治策略令T(n)为分治法计算时间，则a=8,b=2改进：M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7Strassen矩阵乘法效率分析需要进行7次n/2阶矩阵乘积和18次n/2阶矩阵加减运算。a=7,b=2Master定理的应用T(n)=7T(n/2)+n2准备：a=7,b=2f(n)=n2n(logba)=n(log27)比较：

ε=0.1f(n)=n2=O(n(log27)-0.1)结论：T(n)=(n(log27))Strassen矩阵乘法的未来研究矩阵乘法的研究仍然在继续。Hopcroft和Kerr已经于1971年证明：计算2个2乘2阶矩阵乘法需要7次乘法。这说明要想进一步改进矩阵乘法的性能，不能再基于2乘2阶矩阵乘法。在Strassen之后有许多改进算法。在中键入关键字“Strassenmatrix”可搜索到较新的前沿研究成果。返回9.2.4大整数的乘法问题：计算两个n位二进制整数X和Y的乘法。n很大，以至于无法在计算机硬件能直接表示的整数范围内进行处理。可以把X和Y想象成很长的0和1序列。两个一位数的乘法称为位乘法。两个一位数的加法称为位加法。Naïve的解决方案：用小学所学的计算乘积的方法设计XY乘积的算法。X的每一位都要和Y中所有01进行乘积，要进行O(n2)次位乘法，然后再进行n个二进制整数的相加。0110

1010-----------------000001100000+0110-------------------要进行O(n2)次位乘法进行n个二进制整数的相加,要O(n2)次位加法

用分治法解决大整数乘法将n位的二进制整数X和Y都分成2段，每段的长为n/2位。X=Y=X=A*2n/2+B，Y=C*2n/2+DXY=(A*2n/2+B)(C*2n/2+D)=AC2n+(AD+BC)*2n/2+BDA(n/2)位B(n/2)位C(n/2)位D(n/2)位用分治法解决大整数乘法按前式，需要进行4次n/2位整数的乘法，即计算AC，AD，BC和BD需要3次不超过2n位的整数加法，还需要2次移位。一次是移动n位(对应于乘2n)，一次是移动n/2位(对应于乘2n/2)。所有加法和移位共用O(n)步运算。分治法解决大整数乘法的效率设T(n)是2个n位整数相乘所需的运算总数，则有：k=4,m=2,f(n)=n改进XY=(A*2n/2+B)(C*2n/2+D)=AC2n+(AD+BC)*2n/2+BD=AC*2n+((A-B)(D-C)+AC+BD)*2n/2+BD需要作3次乘法，即AC,BD,(A-B)(D-C)，6次加法，2次移位。即k=3，m=2k=3,m=2,f(n)=n返回9.2.5线性时间选择线性时间选择问题的提法元素选择问题的一般提法是:给定线性序集中n个不同的元素和一个整数k，1≼k≼n要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为我们要找的元素。当k=1时,就是要找最小的元素;当k=n时，就是要找最大的元素；当k=(n+1)/2;时，称为找中位数。找n个元素的最小元素和最大元素可以在O(n)时间完成。如果k.log(n)≤n即k≤n/log(n),通过堆排序算法可以在O(n+k.log(n))=O(n)时间内找出第k小元素。先建小头堆，时间耗费O(n)再取k次堆顶元素，时间耗费O(k.log(n))总时间耗费O(n+k.log(n))=O(n)分治算法RandomizedSelect(a,p,r,k)prprRandomizedPartition(a,p,r)i小于等于a[i]的元素个数j=i-p+1大于a[i]的元素个数r-iak<jRandomizedSelect(a,p,i,k)分治算法RandomizedSelect(a,p,r,k)prprRandomizedPartition(a,p,r)i小于等于a[i]的元素个数j=i-p+1大于a[i]的元素个数r-iak>jRandomizedSelect(a,i+1,r,k-j)3,9,1,6,5,4,8,2,10,7ij33,9,1,6,5,4,8,2,10,7jjijijjii3,2,1,6,5,4,8,9,10,7i3,2,1,6,5,4,8,9,10,73,2,1,6,5,4,8,9,10,73,2,1,6,5,4,8,9,10,71,2,3,6,5,4,8,9,10,7如果要找第6小的元素，只需在[6,5,4,8,9,10,7]找第3小的元素如果要找第2小的元素，只需继续在[1，2，3]找第2小的元素一般选择问题的一个分治算法RandomizedSelecttemplate<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i﹣p﹢1;if(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i﹢1,r,k﹣j)}找数组a[0:n-1]第k小元素调用RandomizedSelect(a,0,n-1,k)。算法RandomizdSelect中执行RandomizedPartiton后，数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r],使得a[p:i]中每个元素都不大于a[i+1:r]中每个元素。接着算法计算子数组a[p:i]中元素个数j。如果k≤j,则a[p:i]中第k小元素落在子数组a[p:i]中如果k>j,则要找的第k小元素落在子数组a[i+1:r]中。由于此时已知道子数组a[p:i]中元素均小于要找的第k小的元素，因此，要找的a[p:r]中第k小的元素是a[i+1:r]中的第k-j小的元素。在最坏情况下,算法RandomizedSelect需要Ω(n²)计算时间。例如在找最小元素时，总是在最大元素处划分。(n-1)+(n-2)+…+1=n²算法RandomizedSelect不稳定的原因是由于随机划分函数RandomizedPartition使用了一个随机数产生器Random,它能随机地产生p和r之间的一个随机整数，因此，RandomizedPartition产生的划分基准是随机的。可以证明，算法RandomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。解决算法RandomizedSelect不稳定方法：寻找一个好的划分基准，使得按这个基准所划分出来的两个子数组的长度至少有一个为原数组长度的ε倍(0<ε<1是某个正常数)，那么在最坏情况下用O(n)时间就可以完成选择任务。例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。在最坏情况下，算法所需的计算时间T(n)满足递归式：T(n)≤T(9n/10)+O(n)。由此可得，T(n)=O(n)。寻找一个好的划分基准步骤(1)将n个输入元素划分成n/5个组，每组5个元素，除可能有一组不是5个元素外。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。(2)递归调用Select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的两个中位数中较大的一个。然后以这个元素作为划分基准。其中n个元素用小圆点来表示，绿色小圆点为每组元素的中位数。中位数的中位数x为红色小圆点。图中所画箭头是由较大元素指向较小元素。

x5,6,4,3,7,9,10,1,12,11,13,15,2,8,14[5,6,4,3,7]--------------中位数为5[9,10,1,12,11]--------------中位数为10[13,15,2,8,14]--------------中位数为135,10,13的中位数为10所选的基准元素为105,6,4,3,7,9,10,1,12,11,13,15,2,8,1410,6,4,3,7,9,5,1,12,11,13,15,2,8,1410,6,4,3,7,9,5,1,12,11,13,15,2,8,1410,6,4,3,7,9,5,1,8,11,13,15,2,12,1410,6,4,3,7,9,5,1,8,2,13,15,11,12,142,6,4,3,7,9,5,1,8,10,13,15,11,12,14ijijijij=10/15=2/3,1-=1/3为了简化问题，我们先设所用元素互不相同。找出的基准x至少比3(n－5)/10个元素大：在每一组中有两个元素小于本组的中位数.n/5个中位数中有

(n/5－1)/2=(n-5)/10个小于基准x。比基准x小的元素个数至少为3(n－5)/10。找出的基准x至少比3(n－5)/10个元素小：在每一组中有两个元素大于本组的中位数.n/5个中位数中有

(n/5－1)/2=(n-5)/10个大于基准x。比基准x大的元素个数至少为3(n－5)/10。而当n≥75时，3(n－5)/10≥n/4。所以按此基准划分所得的两个子数组的长度都至少缩短1/4。Template<classType>TypeSelect(Typea[],intp,intr,intk){if(r﹣p<75){

用某个简单排序算法对数组a[p:r]排序；

returna[p﹢k﹣1];};for(inti=0;i<=(r﹣p﹣4)/5;i++)

将a[p﹢5×i]至a[p﹢5×i+4]的第3小元素与a[p﹢i]交换位置；

//中位数的中位数放在a[p,p+(r-p-4)/5].//找中位数的中位数，r﹣p﹣4即上面所说的n﹣5Typex=Select(a,p,p﹢(r﹣p﹣4)/5,(r﹣p﹣4)/10);inti=Partition(a,p,r,x);j=i﹣p﹢1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i﹢1,r,k﹣j);}-------------------------------------------------------------template<classType>intPartition(Typea[],intp,intr,Typex) { inti=p,j=r+1; //将>=x的元素交换到左边区域

//将<=x的元素交换到右边区域

while(true){ while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;rerurnj;}-----------------------------------------------------------------分析算法Select计算时间复杂性为分析算法Select计算时间复杂性,设n=r-p+1，即n为输入数组的长度。算法的递归调用只有在n≥75时才执行。因此，n﹤75时算法Select所用的计算时间不超过一个常数C₁.算法Select的for循环体共执行n/5次，每一次需要O(1)时间。因此，执行for循环共需O(n)时间。找到中位数的中位数x后，算法Select以x为划分基准调用函数Partition对数组a[p:r]进行划分，这需要O(n)时间。设对n个元素的数组调用Select需要T(n)时间.找中位数的中位数x至多用了T(n/5)的时间。我们已经证明了，按照算法所选择的基准x进行划分所得到的两个子数组分别至多有3n/4个元素。所以无论对哪一个子数组调用Select都至多用了T(3n/4)的时间。由此，我们得到关于T(n)的递归式解此递归式可得T(n)=O(n)当元素可能相等时，应在划分之后加一个语句，将所有与基准x相等的元素集中在一起，如果这样的元素个数m≥1，而且j≤k≤j+m-1时，就不必再递归调用，只要返回a[i]即可。否则最后一行改为调用Select(i+m+1,k-j-m)。分治算法Select(a,p,r,k)prprPartition(a