第3章-分治法课件

第3章

分治法

内容提要

一、分治基本思想

二、二分搜索

三、归并排序

四、分治法的基本模式

五、快速排序

六、大整数的乘法

七、矩阵乘法

八、选择问题：找第k小元素

知识要点

分治法的基本模式基本思想适用范围基本步骤应用举例掌握每一个分治算法的基本思想。

学习要求

掌握使用分治策略设计算法的基本思路熟悉典型问题的分治算法将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解决小规模的问题

dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题

returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}分治法的基本步骤人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。

分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素a[mid]，若x=a[mid]，则x在L中的位置就是mid；如果x<a[mid]，由于a是递增排序的，因此假如x在a中的话，x必然排在a[mid]的前面，所以我们只要在a[mid]的前面查找x即可；如果x>a[i]，同理我们只要在a[mid]的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。

分析：很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。据此容易设计出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。找最大最小元素问题

要求在序列A[1..n]中找最小和最大元素。直接求解算法1.算法思想(continue...)

1.x←A[1];y←A[1]；

2.fori←2ton

3.ifA[i]<xthenx←A[i]

4.ifA[i]>ytheny←A[i]

5.endfor

6.return(x,y)

找最大最小元素问题

分治算法

1．基本思想

在序列A[1……n]中找最小和最大元素x,y

if(n<=2)

直接比较得结果;

else

在序列A[1……mid]中找最小和最大元素x1,y1;

在序列A[mid+1…..n]中找最小和最大元素x2,y2

x=min{x1,x2}

y=max{y1,y2};

找最大最小元素问题

2．算法实现

AlgorithmMINMAX

Input:AarrayA[1..n]ofnintegers,wherenisapowerof2.

Output:(x,y):theminimumandmaximumintegersinA.

1.minmax(1,n)

Procedureminmax(low,high)

1.ifhigh-low=1then

2.ifA[low]<A[high]thenreturn(A[low],A[high])

3.elsereturn(A[high],A[low])

4.endif

5.else

6.mid←[(low+high)/2)]

7.(x1,y1)←minmax(low,mid)

8.(x2,y2)←minmax(mid+1,high)

9.x←min{x1,x2}

10.y←min{y1,y2}

11.return(x,y)

12.endif

合并排序二、基本思想：

将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

1．基本思想

将序列A[1……n]中元素排序

[if序列长度n>1

将序列A[1……mid]中元素排序;

将序列A[mid+1…..n]中元素排序

归并两个有序序列A[1……mid]和A[mid+1…..n]；

]一、问题

将序列A[1..n]中元素按照升序排序。合并排序voidMergeSort(Typea[],intleft,intright){

if(left<right){//至少有2个元素intmid=(left+right)/2;//取中点

mergeSort(a,left,mid);

mergeSort(a,mid+1,right);

merge(a,left,mid,right);//合并到数组a}}复杂度分析T(n)=O(nlogn)渐进意义下的最优算法合并排序算法mergeSort的递归过程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]初始序列a[8][4][5][6][2][1][7][3]归并到b[48][56][12][37]复制到a[48][56][12][37]归并到b[4568][1237]复制到a[4568][1237]归并到b[12345678]复制到a[12345678]

归并[4，5，6，8][1，2，3，7]从两个序列的头部开始归并：4与1比较，1被移到结果序列；4与2比较，2被移入结果序列4与3比较，3被放入结果序列；4和7比较，4被放入结果序列,5和7比较...，例如二路归并合并排序

temlplate<classtype>voidMergeSort(Typea[],intleft,intright){if(1eft<right)//至少有2个元素inti=(left+right)/2;//取中点MergeSort(a,1eft,i)；MergeSort(a,i+1,right)；

Merge(a,b,1eft,i,right)；//从a合并到数组bcopy(a,b,left,right);//复制回数组a}}T(n)=dn<=1T(n)=2T(n/2)+cn得:T(n)=(nlogn)分析:算法如下template<classT>voidmerge(TC[],Td[],intl,intm,intr){//把c[l:m],c[m,r]归并到d[l,r]int:i=l,//第—段的游标j=m+1,//第二段的游标k=l;//结果的游标

//只要段中存在i和j,则不断进行归并while((i<=m)&&(j<=r))ifc[i]<=c[j]d[k++]=C[i++]：elsed[k++]=C[j++]：

//考虑余下的部分if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q]；elsefor(intq=i;q<=m；q++)d[k++]=c[q]；}合并排序最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空间：O(n)分治法的基本模式

一、分治法的基本思想及其适用范围

君主和殖民者所运用的分而治之这一古老的策略也可以被用来设计高效率的计算机算法。分而治之方法与软件设计的模块化方法非常相似。为了解决一个大问题，其基本思想为：把它分成两个或多个更小的问题；分别解决每个小问题；各个小问题的解答组合起来即可得到原问题的解答。

小问题通常与原问题类似，可以递归地使用分而之治策略来解决。

分治法的关键步骤是：划分处理子问题合并分治法的基本模式分治法的基本模式

二、分而治之法算法的模式

若问题实例I大小“较小”，则直接求解并返回结果；否则进行下一步；（divide）将I分成m个大小基本相同的子实例I1,I2,…,Im；（conquer）对于每个子实例递归地求解得到它们的解；（combine）将子实例的解合并得到实例I的解。

大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:X=Y=X=a2n/2+bY=c2n/2+d

XY=ac2n+(ad+bc)2n/2+bd

abcd复杂度分析T(n)=O(n2)没有改进大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd

为了降低时间复杂度，必须减少乘法的次数。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法??如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法。{S=SIGN(X)*SIGN(Y)；X:=ABS(X)；Y:=ABS(Y)；ifn=lthenif(X=1)and(Y=1)thenreturn(S)elsereturn(0)else{A:=X的左边n/2位；B:=X的右边n/2位；C:=Y的左边n/2位；D:=Y的右边n/2位；m1:=MULT(A，C，n/2)；m2:=MULT(A-B,D-C，n/2)；m3:=MULT(B，D，n/2)；S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)；return(S)}}{X,Y为2个小于2n的二进制整数，返回结果为X和Y的乘积XY}intfunctionMULT(X,Y,n)大数相乘的分治递归算法二进制大整数乘法同样可应用于十进制大整数的乘法存放XY的符号存放三个乘积算法Strassen矩阵乘法A和B的乘积矩阵C中的元素C[i,j]定义为:

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3)传统方法：O(n3)Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：传统方法：O(n3)分治法:由此可得：复杂度分析T(n)=O(n3)Strassen矩阵乘法传统方法：O(n3)分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进procedureSTRASSEN(n,A,B,C)；{ifn=2thenMATRIX_MULTIPLY(A,B,C)else{将矩阵A和B分块；STRASSEN(n/2，A11，B12-B22，M1)；STRASSEN(n/2，A11+A12，B22，M2)；STRASSEN(n/2，A21+A22，B11，M3)；STRASSEN(n/2，A22，B21-B11，M4)；STRASSEN(n/2，A11+A22，B11+B22，M5)STRASSEN(n/2，A12-A22，B21+B22，M6)；STRASSEN(n/2，A11+A21，B11+B12，M7)C:=矩阵相乘Strassen算法T(n)=T(2)=O(1)T(n)=7T(n/2)+18(n/2)2得:T(n)=O(nlog7)=O(n2.81)分析:

算法快速排序一、算法思想

快速分类算法是由著名的计算机科学家霍尔（C.A.R.Hoare）根据分治策略设计的一种高效率的分类算法。基本思想是，对于输入的子序列A[p..q]，快速分类分三步走：分解(Divide)：将A[p..q]划分成两个非空的子序列A[p..j]和A[j+1..q]，使得A[p..j]中的任一元素小于或等于A[j+1..q]中的任一元素。下标j在划分过程中确定.

具体的划分过程可由如下的方法来实现：选取A[p..q]的某个元素v，然后将其它元素重新排列，使A[p..q]中所有在v以前出现的元素都小于或等于v，而所有在v后面出现的元素都大于或等于v。集合的这种重新整理叫做划分，而元素v称为划分元素。递归求解(Conquer)：通过递归调用快速分类算法分别对A[p..j-1]和A[j+1..q]进行分类合并(Merger)：由划分的特点知，在A[p..j-1]和A[j+1..q]都分好类后不需任何算A[p..q]就已分好类。快速排序

在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Split(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}快速排序template<classType>intSplit(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将<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;returnj;}初始序列{6,7,5,2,5,8}j--;{5,7,5,2,6,8}i++;{5,6,5,2,7,8}j--;{5,2,5,6

,7,8}i++;完成{6,7,5,2,5,8}{5,2,5}6

{7,8}方法一：快速排序

AlgorithmSPLIT

Input:AarrayofelementsA[low..high].

Output:(1)Awithitselementsrearranged,ifnecessary,asdecribedabove

(2)w,thenewpositionofthesplitingelementA[low].

1.i←low 2.x←A[low] 3.forj←low+1tohigh 4.ifA[j]≤xthen 5.i←i+1

6.ifi≠jtheninterchangeA[i]andA[j] 7.endif 8.endfor

9.interchangeA[low]andA[i]

10.w←i

11.returnAandw方法二：快速排序template<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}快速排序

快速排序算法的性能取决于划分的对称性。通过修改算法Split

，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)快速排序选择问题:找中值和第k小元素

一、选择问题

找出序列A[1..n]中的第k小元素。特别地，当k=n/2时，即找中值元素。二、算法1——排序算法

时间复杂度:(nlogn)

三、算法2————最坏时间复杂度为O()的分治法算法思想如下：选择问题:找中值和第k小元素

1．算法思想

对于集合A[1..n]中的元素，用其中某元素v进行划分：

A1={a|a<v且aA}，

A2={a|a=v且aA}，

A3={a|a>v且aA}。

case|A1|k：问题归结为在A1中找第k小元素；

case|A1|+|A2|>=k：v就是第k小元素；

case|A1|+|A2|<k：问题归结为在A3中找第k-|A1|-|A2|小元素。

对于第一、第三种情形，在A1或A3上重复上述过程直到找到所要找的元素为止。

2．最坏时间复杂度:O()选择问题分治算法思路:模仿快速排序对输入数组A进行二分划分,使子数组A1的元素<=A2中的元素,分点J由随机数产生,若KJ,则K为A1的第K小元,若K>J,则K为A2的第K-J小元.与快速排序算法不同,它只对子数组之一进行递归处理。分析:template<classType>TypeRandomizedSelect(a[],intleft,intright,intk){if(left==right)returna[left];inti=RandomizedPartition(a,left,right),j=i-left+l;if(k<=j)returnRandomizedSelect(a,left,i,k);elsereturnRandomizedSelect(a,i+1,right,k-j);}Tmax=

(n2)(左半总为空)若分点总是等分点,则Tmin(n)=dT(n)=T(n/2)+cn得:T(n)=(n)最坏情况下的选择算法:通过寻找一个好的划分基数,可使最坏情况下时间为O(n).例如:考察如下情形:r=5,n=27,a=[2,6,8,1,4,10,20,6,22,11,9,8,4,3,7,8,16,11,10,8,2,14,15,1,12,5,4]。算法思路(中间的中间):将a中元素分为n/r组,除最后一组外每组元素为r个.通过对每组排序找到各组的中位数,根据n/r个中位数递归使用选择算法得到支点元素.分组: