第二讲-分治专题讲座ppt课件

算法设计与分析,第二讲分治,目的分治法的思想分治算法的设计方法将递归算法改写成迭代算法的一般方法重点分治法的抽象控制策略针对问题的抽象控制策略实现难点将递归算法改写成迭代算法的一般方法和实现,2.1基本策略,一、求解大规模问题的复杂性,二、化整为零、分而治之,Pn,p1n1,p2n2,pknk,s0,s1,sk,S,分解,分治,合并,三、分治法的抽象控制策略,设：原问题输入为an，简记为(1，n)；子问题输入为apaq，1pqn，简记为(p，q)。,已知：SOLUTION;intdivide(int,int);intsmall(int,int);SOLUTIONconquer(int,int);SOLUTIONcombine(SOLUTION,SOLUTION);,SOLUTIONDandC(p,q)/*divideandconquer*/if(small(p,q)returnconquer(p,q);elsem=divide(p,q);returncombine(DandC(p,m),DandC(m+1,q);,分治法的抽象控制算法,已知n个按非降次序排列的元素an,查找元素x是否在表中出现,若找到,返回其下标值,否则,返回一负数.,2.2二分检索,一、问题,二、分治的思路,原问题:(n,a0,an-1,x),数据分组:a0ak-2ak-1akan-1,三个子问题:(k-1,a0,ak-2,x)(1,ak-1,x)(n-k,ak,an-1,x),intBinSearch1(p,q,x)intk=(p+q)/2;if(qak)returnBinSearch1(k+1,q,x);,三、递归算法,四、计算复杂度,1.二元比较树,以有序表的中间元素为根节点的二分树,左子树上所有元素不比父节点元素值大,右子树上所有元素不比父节点元素值小,圆形接点称为内节点,对应成功检索的数据元素,二分检索树的深度:,二元比较树的深度:,方形接点称为外节点,对应不成功检索的数据子集,定理2.2若n在区域2k-1,2k)中,则对于一次成功的检索,BinSearch1至多作k次比较;而对于一次不成功的检索,或者作k-1次比较或者作k次比较。,成功检索最好情况:不成功检索最好情况:成功检索最坏情况:不成功检索最坏情况:,2.时间复杂度,平均情况分析,内部路径长度之和：I,5,2,7,1,3,6,8,4,9,外部路径长度之和：E,E=I+2n。,成功检索的平均比较次数：S(n)=(I/n)+1,不成功检索的平均比较次数:U(n)=E/(n+1),因为：U(n)=O(logn)，所以：S(n)=O(logn),由此可得：S(n)=(1+1/n)U(n)-1,成功检索不成功检索最好最坏平均最好最坏平均O(1)O(logn)O(logn)O(logn)O(logn)O(logn),二分检索的时间复杂度结论,定理2.3设an含有n(n1)个不同元素,排序为a1*max)*max=ai;elseif(ai*min)*min=ai;,直接搜索的改进方法,三、实现分治的递归算法,集合只有一个元素时*max=*min=ai；,集合只有两个元素时if(aiaj)*max=aj;*min=ai;else*max=ai;*min=aj;,集合中有更多元素时分治:将原集合分解成两个子集,分别求两个子集的最大和最小元素,再合并结果。,递归算法,typedefstructElemTypemax,min;SOLUTION;,SOLUTIONMaxMin(i,j)SOLUTIONs,s1,s2;if(i=j)s.max=s.min=ai;returns;if(i=j-1)if(ai=s2.max)?(s.max=s1.max):(s.max=s2.max);(s1.min=j-1)/*对应一元素和两元素的情况*/if(aiaj)s.max=aj;s.min=ai;elses.max=ai;s.min=aj;returns;,MaxMin需要的比较次数,存在下列递推关系：,思考题请分析c(n)递推关系式中为什么是加3而不是加2?,给定一个含n个元素的集合an,按一定次序(本课程假定均为非降次序)将其分类(排序)。,2.4分类,一、问题,二、插入分类,基本思想,InsertSort(intn)for(j=1;j=0),插入分类算法,三、归并分类,基本思想,归并分类递归算法,MergeSort(l,h)if(lh)m=(l+h)/2;MergeSort(l,m);MergeSort(m+1,h);Merge(l,m,h);,已分类子集的归并过程,Merge(low,mid,high)ElemTypebn;l=low;h=mid+1;k=l;while(lmid)while(h=high)bk+=ah+;/*转储剩余部分*/elsewhile(l=mid)bk+=al+;alow:high=blow:high;/*将b数组转储到a*/,已分类子集的归并算法,时间复杂度,缺点与改进,结合插入分类与归并分类各自的优点,四、快速分类,设计思路,实现部分分类的划分过程举例,实现部分分类的划分算法,Partition(p,q)r=ap;j=p+1;k=q;while(1)while(j=r)k-;if(jk)t=aj;aj=ak;ak=t;j+;k-;elsebreak;ap=ak;ak=r;returnk;,快速分类算法,QuickSort(p,q)if(pq)j=Partition(p,q);QuickSort(p,j-1);QuickSort(j+1,q);,时间复杂度,最坏情况：CW(n)=n+n-1+3+2=O(n2).,假设n个元素各不相同，划分元素随机选取，取第k(1kn)个元素是等概率的，计算时间C(n)取决于Partition的元素比较次数.,平均情况：,经推导可得:CA(n)ak)k=j;returnk;,优化后的迭代算法,例3：将分治算法的抽象递归过程改写为迭代过程。,SOLUTIONDandC(p,q)/*divideandconquer*/intm;SOLUTIONs1,s2,s;if(small(p,q)s=conquer(p,q);elsem=divide(p,q);s1=DandC(p,m);s2=DandC(m+1,q);s=combine(s1,s2);returns;,抽象控制递归算法,SOLUTIONDandC(p,q)externElemTypestack5*n+1,top=0;intm;SOLUTIONs1,s2;L1:if(small(p,q)s=conquer(p,q);elsem=divide(p,q);stack+top=p;stack+top=q;stack+top=m;stack+top=L2;p=p;q=m;gotoL1;L2:s1=stacktop-;stack+top=p;stack+top=q;stack+top=m;stack+top=L3;p=m+1;q=q;gotoL1;L3:s2=stacktop-;s=combine(s1,s2);,if(top=0)returns；elseaddr=stacktop-;m=stacktop-;q=sta