算法设计与分析-王红梅-第二版-第4章-分治法

第4章分治法算法设计与分析—本科生课程DesignandAnalysisofAlgorithm海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversity2019/10/14DivideandConquerMethod2本章要点4.1概述4.2排序问题中的分治法4.3组合问题中的分治法4.4几何问题中的分治法阅读材料递归函数的执行过程2019/10/14DivideandConquerMethod3教学重点分治法的设计思想，各种经典问题的分治思想教学难点几何问题的分治算法教学内容及目标知识点教学要求了解理解掌握熟练掌握分治法设计思想√归并排序和快速排序√最大子段和问题√棋盘覆盖问题√最近对问题√凸包问题√学习目标2019/10/14DivideandConquerMethod44.1.1分治法的设计思想4.1.2分治法的求解过程概述2019/10/14DivideandConquerMethod5将一个难以直接解决的大问题，划分成一些规模较小的子问题，以各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。分治法的设计思想：概述-分治法思想2019/10/14DivideandConquerMethod62.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。1.平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2、4,…），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。启发式规则：概述-分治法思想2019/10/14DivideandConquerMethod7子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况概述-分治法思想2019/10/14DivideandConquerMethod8一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。概述-分治法的求解过程2019/10/14DivideandConquerMethod9概述-分治法的求解过程分治法的一般过程1DivideConquer(P)//求解规模为n的问题P2{3if(P的规模足够小)直接求解P;分解为k个子问题P1,P2,…,Pk;4for(i=1;i=k;i++)5yi=DivideConquer(P);//解各子问题，通常采用递归6returnMerge(y1,y2,…,yk);//将各子问题的解合并为原问题的解7}例：计算an，应用分治技术得到如下计算方法：3432328131319313193333分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。时间性能O(nlog2n)而蛮力法的时间性能为O(n)*==1122naanaannn如果如果2019/10/14DivideandConquerMethod114.1.1分治法的设计思想4.1.2一个简单的例子——数字旋转方阵概述2019/10/14DivideandConquerMethod12[问题]输出如图4.3(a)所示N*N（1≤N≤10）的数字旋转方阵[思路]用二维数组表示方阵，从外层向里层填数，如图(b)所示，将每一层的填数过程分为ABCD四个区域。每填一层size减2，终止条件是size≤1。数字旋转方阵2019/10/14DivideandConquerMethod13算法4.1：数字旋转方阵Full输入：当前层左上角要填的数字number，左上角的坐标begin，方阵的阶数size输出：数字旋转方阵1.如果size=0，则算法结束；2.如果size=1，则data[begin][begin]=number，算法结束；3.初始化行、列下标i=begin，j=begin；4.重复下述操作size-1次，填写区域A1.Data[i][j]=number;number++;i++;数字旋转方阵2019/10/14DivideandConquerMethod145.重复下述操作size-1次，填写区域B1.Data[i][j]=number;number++;j++;6.重复下述操作size-1次，填写区域C1.Data[i][j]=number;number++;i--;7.重复下述操作size-1次，填写区域D1.Data[i][j]=number;number++;j--;8.递归调用函数Full在size-2阶方阵中左上角begin+1处从数字number开始填数数字旋转方阵2019/10/14DivideandConquerMethod15[算法分析]填写n阶方阵，四个区域由4个循环实现，每个循环均执行n-1，然后执行递归调用，填写n-2阶方阵。递推式：数字旋转方阵=T(n-2)+4(n-1)当n=0时0nT1)(当n=1时当n1时设n为偶数，用扩展递归技术解此递推式，得T(n)=T(n-2)+4(n-1)=T(n-4)+4(n-3)+4(n-1)=T(0)+…+4(n-5)+4(n-3)+4(n-1)=O(n2)2019/10/14DivideandConquerMethod16本章要点4.1概述4.2排序问题中的分治法4.3组合问题中的分治法4.4几何问题中的分治法阅读材料递归函数的执行过程2019/10/14DivideandConquerMethod17排序问题中的分治法4.2.1归并排序4.2.2快速排序2019/10/14DivideandConquerMethod18归并排序二路归并排序的分治策略是：（1）划分：将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。4.2.1归并排序2019/10/14DivideandConquerMethod19r1……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合并解4.2.1归并排序2019/10/14DivideandConquerMethod20[想法]首先将序列划分为两个子序列，如子序列长度为1，则划分结束，否则继续执行划分，结果将具有n个待排序的记录序列划分为n个长度为1的有序子序列；然后两两合并，得到n/2个长度为2的有序子序列，再进行两两合并…直到得到一个长度为n的有序序列。4.2.1归并排序2019/10/14DivideandConquerMethod21算法4.3——归并排序voidMergeSort(intr[],intr1[],ints,intt)//r[]—原序列数组，r1[]—归并后序列数组{if(s==t)r1[s]=r[s];else{m=(s+t)/2;Mergesort(r,r1,s,m);//归并排序前半个子序列Mergesort(r,r1,m+1,t);//归并排序后半个子序列Merge(r1,r,s,m,t);//合并两个已排序的子序列}}4.2.1归并排序r[s],…,r[m]r[m+1],…,r[t]2019/10/14DivideandConquerMethod22算法4.4——合并有序子序列voidMerge(intr[],intr1[],ints,intm,intt){//i,j分别指向两个待合并的有序子序列，k指向最终有序序列的当前记录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++];}4.2.1归并排序ijr[s],…,r[m]r[m+1],…,r[t]kr1[s],…,r1[m],r1[m+1],…,r1[t]2019/10/14DivideandConquerMethod23二路归并排序的合并步骤的时间复杂性为O(n)，所以，二路归并排序算法存在如下递推式：根据2.1.5节的通用分治递推定理，二路归并排序的时间代价是O(nlog2n)。+==2)2(221)(nnnTnnT4.2.1归并排序2019/10/14DivideandConquerMethod24（2）求解子问题：分别对划分后的每一个子序列递归处理；（3）合并：由于对子序列r1…ri-1和ri+1…rn的排序是就地进行的，所以合并不需要执行任何操作。快速排序的分治策略（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1…ri-1和ri+1…rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；4.2.2快速排序[r1……ri-1]ri[ri+1……rn]均≤ri轴值均≥ri位于最终位置2019/10/14DivideandConquerMethod25以第一个记录为轴值（可随机），对待排序序列进行划分的过程：（1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j--,即前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换；（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i++，即后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换；4.2.2快速排序2019/10/14DivideandConquerMethod26（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。4.2.2快速排序一次划分示例:（1）i=1,j=7，r[1]为基准记录;（2）r[i]r[j]?j--:r[i]r[j]//右侧扫描（3）r[i]r[j]?i++:r[i]r[j]//左侧扫描（4）i=j?ifi=j,then第一次划分基准记录位置找到2019/10/14DivideandConquerMethod2713652750384955jijj13652750384955jiii13652750384955ijjj一次划分示例2019/10/14DivideandConquerMethod28算法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];//将