算法-分治法

2020/6/16分治法第4章分治法4.1概述4.2排序问题中的分治法4.3组合问题中的分治法4.4几何问题中的分治法分治法是最著名的算法设计技术。1/562020/6/16分治法4.1概述4.1.1分治法的设计思想4.1.2数字旋转方阵2/562020/6/16分治法将一个难以直接解决的大问题，划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。4.1.1分治法的设计思想如果子问题的规模仍然不够小，可继续分解下去。3/562020/6/16分治法分治法的求解过程：分-治-合（1）划分：把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题。（3）合并：把各个子问题的解合并起来，分治算法的有效性很大程度上依赖于合并的实现。4/562020/6/16分治法2.独立子问题：各子问题之间相互独立。1.平衡子问题：最好使子问题的规模大致相同。启发式规则：5/562020/6/16分治法子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况6/562020/6/16分治法例：计算an，应用分治技术得到如下计算方法：3432328131319313193333分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能´==1122naanaannn如果如果7/562020/6/16分治法4.1.2数字旋转方阵问题：输出NN(1N10)数字旋转方阵。12019181716221323130153223336291442334352813524252627126789101166的旋转方阵8/562020/6/16分治法4.2排序问题中的分治法4.2.1归并排序4.2.2快速排序92020/6/16分治法4.3.1归并排序二路归并排序的分治策略是：（1）划分：将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。10/562020/6/16分治法r1……rn/2rn/2＋1……rn划分r‘1……r’n/2r’n/2＋1……r’n递归处理r''1……r''n/2r''n/2＋1……r''n合并解举例：8326715411/562020/6/16分治法算法4.3——归并排序voidMergeSort(intr[],ints,intt){intm,r1[1000];if(s==t)return;else{m=(s+t)/2;Mergesort(r,s,m);//归并排序前半个子序列Mergesort(r,m+1,t);//归并排序后半个子序列Merge(r,r1,s,m,t);//合并两个已排序的子序列for(inti=s;i=t;i++)//将有序序列传回数组r中r[i]=r1[i];}}12/562020/6/16分治法二路归并排序的合并步的时间复杂性为O(n)，所以，二路归并排序算法存在如下递推式：可得二路归并排序的时间代价是O(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性为O(n)。+==1)2(211)(nnnTnnT13/562020/6/16分治法算法4.4——合并有序子序列voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i=m&&j=t){if(r[i]=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小者放入r1[k]elser1[k++]=r[j++];}if(i=m)while(i=m)//若第一个子序列没处理完，则进行收尾处理r1[k++]=r[i++];elsewhile(j=t)//若第二个子序列没处理完，则进行收尾处理r1[k++]=r[j++];}14/562020/6/16分治法4.3.2快速排序（2）求解子问题：分别对划分后的每一个子序列递归处理；（3）合并：由于对子序列r1…ri-1和ri+1…rn的排序是就地进行的，所以合并不需要执行任何操作。快速排序的分治策略是：（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列；15/562020/6/16分治法[r1……ri-1]ri[ri+1……rn]均≤ri轴值均≥ri位于最终位置归并排序按照记录在序列中的位置对序列进行划分，快速排序按照记录的值对序列进行划分。16/562020/6/16分治法以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化：取第一个记录作为基准，设置两个参数i，j；（2）右侧扫描过程：（3）左侧扫描过程：（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。172020/6/16分治法13652750384955jijj13652750384955jiii13652750384955ijjj一次划分示例182020/6/16分治法算法4.5——一次划分intPartition(intr[],intfirst,intend){i=first;j=end;//初始化while(ij){while(ij&&r[i]=r[j])j--；//右侧扫描if(ij){r[i]←→r[j];//将较小记录交换到前面i++;}while(ij&&r[i]=r[j])i++；//左侧扫描if(ij){r[j]←→r[i];//将较大记录交换到后面j--;}}retutni;//i为轴值记录的最终位置}192020/6/16分治法以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。132750384955jiij1365275038495565202020/6/16分治法算法4.6——快速排序voidQuickSort(intr[],intfirst,intend){if(firstend){pivot=Partition(r,first,end);//问题分解，pivot是轴值在序列中的位置QuickSort(r,first,pivot-1);//递归地对左侧子序列进行快速排序QuickSort(r,pivot+1,end);//递归地对右侧子序列进行快速排序}}212020/6/16分治法T(n)=2T(n/2)＋n=2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n=4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n………=nT(1)＋nlog2n＝O(nlog2n)因此，时间复杂度为O(nlog2n)。最好情况:每次划分后把待划分区间划分为长度相等的两个子序列。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时间为O(n)。设T(n)是对n个记录的序列进行排序的时间，则有：222020/6/16分治法因此，时间复杂度为O(n2)。最坏情况：待排序记录序列正序或逆序。此时，必须经过n-1次递归调用，而且第i趟划分需要经过n-i次关键码的比较，因此，总的比较次数为：)()1(21211nOnninni===）（232020/6/16分治法平均情况：设基准记录的关键码第k小(1≤k≤n)，则有：这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为O(nlog2n)。+=++===nknknkTnnkTknTnnT11)(2))1()((1)(快速排序的空间复杂性如何?24/562020/6/16分治法4.3组合问题中的分治法4.3.1最大子段和问题4.3.2棋盘覆盖问题补充：循环赛日程安排问题25/562020/6/16分治法给定由n个整数组成的序列(a1,a2,…,an)，最大子段和问题要求该序列形如的最大值(1≤i≤j≤n)。当序列中所有整数均为负整数时，其最大子段和为0。如，序列(-20,11,-4,13,-5,-2)的最大子段和为：4.3.1最大子段和问题=jikka==4220kka26/562020/6/16分治法最大子段和问题的分治策略是：（1）划分：按照平衡子问题的原则，将序列(a1,a2,…,an)划分成长度相同的两个子序列(a1,…,a)和(a＋1,…,an)，则：2n2n先考虑最大子段和问题的简单算法27/562020/6/16分治法①a1,…,an的最大子段和＝a1,…,a的最大子段和；②a1,…,an的最大子段和＝a＋1,…,an的最大子段和；③a1,…,an的最大子段和＝，且2n2n=jikkanjnni+12,21（2）求解子问题：对于划分阶段的情况①和②可递归求解，情况③需要分别计算，，则s1+s2为情况③的最大子段和。（3）合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的较大者为原问题的解。)21(max12niasnikk==+=+=jnkknjnas12)12(max2282020/6/16分治法a1……ai…amidamid+1…aj……an划分leftsumrightsum递归处理a1……ai…amidamid+1…aj……an最大子段和横跨两个子序列sum不能递归处理max{leftsum,sum,rightsum}合并解)2(nmid=292020/6/16分治法算法4.7——最大子段和问题intMaxSum(inta[],intleft,intright){sum=0;if(left==right){//如果序列长度为1，直接求解if(a[left]0)sum=a[left];elsesum=0;}else{center=(left+right)/2;//划分leftsum=MaxSum(a,left,center);//对应情况①，递归求解rightsum=MaxSum(a,center+1,right);//对应情况②，递归求解302020/6/16分治法s1=0;lefts=0;//以下对应情况③，先求解s1for(i=center;i=left;i--){lefts+=a[i];if(leftss1)s1=lefts;}s2=0;rights=0;//再求解s2for(j=center+1;j=right;j++){rights+=a[j];if(rightss2)s2=rights;}sum=s1+s2;//计算情况③的最大子段和if(sumleftsum)sum=leftsum;//合并，在sum、leftsum和rightsum中取较大者if(sumrightsum)sum=rightsum;}returnsum;}31/562020/6/16分治法算法的时间性能：对应划分得到的情况①和②，需要分别递归求解，对应情况③，两个并列for循环的时间复杂性是O(n)，所以，存在如下递推式：+==1)2(211)(nnnTnnT从而可得算法4.7的时间复杂性为O(nlog2n)。322020/6/16分治法4.3.2棋盘覆盖问题在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用图（b）所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。(a)k=2时的一种棋盘(b)4种不同形状的L型骨牌332020/6/16分治法分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k0时，可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘，这样划分后，由于原棋