第3章分治法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 分治法,“分”而治之,2.1 一般方法,对大规模问题的求解,利用分治法求解大规模问题,1.,基本思想,分而治之方法法与软件设计的模块化方法非常相似。为解决一个大问题，可以,（1）把它,分解,成两个或多个更小的问题；（2）,分别解决,每个小问题；（3）把各小问题的解答,组合,起来，即可得到原问题的解。,小问题通常与原问题相似或同质,，因而可以,递归,地使用分而治之策略解决。,12/12/2025,本章教学要求及重点难点,理解分治法的基本思想,掌握二分检索中成功检索和不成功检索各自时间复杂度的计算方法,掌握归并分类的基本方法,掌握快速分类的算法及对此算法的时间复杂度分析,掌握最坏情况下选择问题的时间复杂度分析,重点：二分检索、找最大和最小元素、归并分类、快速分类。,难点：选择问题的算法及对该算法的时间复杂度分析,12/12/2025,通常，子问题与原始问题“,同质”,12/12/2025,例,找伪币,假设16 枚金币中有一枚是伪造的，真假金币的区别仅是重量不同(伪币轻一些），利用一个没有砝码的天平作工具，找出这枚伪造的金币。,方法1：比较硬币1和2的重量，有一个轻则找到；否则比较硬币3和4，依次比较下去，直到找到。最多8次比较。,方法2：利用分治法。16个硬币分为两组，每组8个，比较重量伪币在轻的一组。将轻的一组再分为两组，每组4个继续划分下去，依次每组2个，每组1个，此时找到。,12/12/2025,算法2.1 分治策略的抽象化控制,procedure DANDC(p,q),global n,A(1:n);,integer m,p,q;/1,pqn,/,if SMALL(p,q),then return(G(p,q),else,m,DIVIDE(p,q)/p,mq,/,return(COMBINE(DANDC(p,m),DANDC(m+1,q),endif,end DANDC,注：,k=2:,二分,是最常用的分解策略；,SMALL(p,q)：,布尔函数，判断输入规模q-p1是否足够小而无需再进一步分就可求解；,G(p,q)：,对输入规模为q-p+1的子问题求解（SMALL(p,q)为真时）；,DIVIDE(p.q)：,对输入规模为q-p+1的子问题进一步分解，返回值为p,q区间进一步的分割点（SMALL(p,q),不,为真时,）,；,COMBINE(x,y)：,子结果的合并函数，将区间p,m和m+1,q上的子问题的解合并成上级区间p,q上的“较完整”的解。当p=1,q=n时，就得到整个问题的解。,2.分治策略的抽象化控制,12/12/2025,分治求解策略分析,：,定义问题的,形式描述,：I=(n,a,1,a,2,a,n,x),问题分解：选取下标k，由此将I分解为,3,个子问题：,I,1,=(k-1,a,1,a,2,a,k-1,x),I,2,=(1,a,k,x),I,3,=(n-k,a,k+1,a,k+2,a,n,x),对于I,2,，若a,k,=x，则有解k，对I,1,、I,3,不用再求解；否则，,若xa,k,，则只在I,3,中求解，对I,1,不用求解；,I,1,、I,3,上的求解可再次采用分治方法划分后求解（,递归过程,）,12/12/2025,2.二分检索算法,算法2.3 二分检索,procedure BINSRCH(A,n,x,j),integer low,high,mid,j,n;,low,1;,high,n;,while lowhigh do,mid,case,:xA(mid):low mid+1,:else:jmid;return,endcase,repeat,j0,end BINSRCH,注,：,给定一个按非降次序排列的元素数组A(1:n)，n,1,判断x是否出现。,若是，置,j,，,使得,x=A(j),若非，,j=0,12/12/2025,例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101),在A中检索x=101，-14，82。执行轨迹见下表1,成功,的检索,不成功,的检索,成功,的检索,12/12/2025,3.算法的正确性证明,定理2.1 过程BINSRCH(A,n,x,j)能正确运行,证明：,1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都,能按要求正确运行即首先满足确定性和能行性,2）终止性,算法初始部分置low,1,highn,若n=0，不进入循环，j置0，算法终止,否则，进入循环，计算mid,或 x=A(mid)，j置为mid，算法终止；,或xA(mid)，置low,mid+1，进入下次循环；搜索范围实际缩小,为mid+1,high，对low,mid-1区间不做进一步搜索；,因low,high,mid都是整型变量，故按照上述规则，在,有限步内,，或找到某个mid，有A(mid)=x；或变得lowhigh，在A中没有找到任何元素等于x，算法终止。,12/12/2025,4.性能分析,1）空间特性,n+5个空间位置,(n),2)时间特性,区分以下情况，并进行相应的分析,成功检索,：所检索的x出现在A中。,成功检索情况共有,n种,：x恰好是A中的某个元素，A中共有n个元素，故有n种可能的情况,不成功检索,：所检索的x不出现在A中。,不成功检索情况共有,n+1种,：xA(n),成功/不成功检索的最好情况,：执行步数最少，计算时间最短,成功/不成功检索的最坏情况,：执行步数最多，计算时间最长,成功/不成功检索的平均情况,：一般情况下的计算时间,12/12/2025,实例分析（例2.1）,频率计数特征,while,循环体外语句的频率计数为,1,集中考虑while,循环中的,x,与,A,中元素的比较（其它运算的频率计数与之有相同的数量级）,假定只需一次比较就可确定,case,语句控制是三种情况的哪一种。查找每个元素所需的元素比较次数统计如下：,A,元素 -15 -6 0 7 9 23 54 82 101,成功检索,比较次数,3 2 3 4 1 3 2 3 4,不成功检索,比较次数,3 3 3 4 4 3 3 3 4 4,12/12/2025,成功检索,最好,：,1次,最坏,：,4次,平均,：（3+2+3+4+1+3+2+3+4）/9,2.77次,不成功检索,最好,：,3次,最坏,：,4次,平均,：(3+3+3+4+4+3+3+3+4+4)/10=,3.4次,12/12/2025,二元比较树,算法执行过程的,主体,是x与一系列中间元素A(mid)比较。可用一棵二元树描述这一过程，并称之为,二元比较树,。,构造,：比较树由称为,内结点,和,外结点,的两种结点组成：,内结点,：表示一次元素比较，用圆形结点表示，存放一个mid值；代表一次成功检索；,外结点,：在二分检索算法中表示一种不成功检索的情况，用方形结点表示。,路 径,：表示一个元素的比较序列。,例2.1的二元比较树,12/12/2025,基于二元比较树的分析,若x在A中出现，则算法的执行过程在一个圆形的,内结点,处结束。,若x不在A中出现，则算法的执行过程在一个方形的,外结点,处结束,外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。,例2.1的二元比较树,12/12/2025,定理2.2 若n在区域2,k-1,2,k,)中，则对于,一次成功的检索,，BINSRCH至多做,k,次比较；对于,一次不成功的检索,，或者做,k-1,次比较，或者做,k,次比较。,证明：,要点：,成功检索都在内结点处结束，不成功检索都在外结点处结束,当2,k-1,n,2,k,时，所有内结点在1至k级，所有外结点在第k级,或第k+1级，,故：成功检索在i级终止所需要的元素比较次数是i,不成功检索在i级外部结点终止的元素比较次数是i-1,12/12/2025,BINSRCH计算复杂度的理论分析,1）不成功检索的最好、最坏和平均情况的计算时间均为 外结点处在最末的两级上；,2）最好情况下的成功检索的计算时间为,最坏情况下的成功检索的计算时间为,12/12/2025,3）平均情况下的成功检索的计算时间分析,利用,外部结点和内部结点到根距离和之间的关系,进行推导：,记，,由根到所有内结点的距离之和称为,内部路径长度,，记为,I,；,由根到所有外部结点的距离之和称为,外部路径长度,，记为,E,。,则有，,E=I+2n,记，,U(n),是平均情况下不成功检索的计算时间，则,U(n)=E/(n+1),S(n),是平均情况下成功检索的计算时间，则,S(n)=I/n+1,利用上述公式，可有:,S(n)=(1+1/n)U(n)-1,当n,S(n)U(n),，而U(n)=,所以 S(n)=,12/12/2025,4.以比较为基础检索的时间下界,问题,：设n个元素的数组A(1:n)有A(1)A(2)A(n)。检索一给定元素x是否在A中出现。,定理2.2给出了二分检索算法的时间下界，是否预计还存在有以元素比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有,更低,的数量级?,以比较为基础的算法,：假定算法中只允许进行元素间的,比较,，而不允许对它们实施其它运算。,12/12/2025,注：每个,内结点,表示一次元素的比较。每棵比较树中恰好含有,n,个内结点，分别与n个不同i值相对应；每个,外结点,对应一次不成功的检索，并恰好又,n+1,个外结点对应于n+1中不成功检索的情况。,任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。,12/12/2025,以比较为基础的有序检索问题最坏情况的时间下界,定理2.3 设A(1:n)含有 n(n,1)个不同的元素，排序为,A(1)A(2)max then,maxA(i),endif,if A(i)max then maxA(i)endif,else if A(i)min then minA(i)endif,repeat,end STRAITMAXMIN1,这使得，,最好情况：,按,递增次序,排列元素比较次数为,n-1,次,最坏情况：,按,递减次序,排列，元素比较次数为,2(n-1),次,平均情况：,元素比较次数为,3(n-1)/2,次,12/12/2025,2.分治求解策略,记问题的一个实例为：,I=(n,A(1),A(n),采用二分法将I分成两个子集合处理,I,1,=(,A(1),，A()，和,I,2,=(n-,A(+1),，A(n),则有，,MAX(I)=,max,(MAX(,I,1,),MAX(,I,2,),MIN(I)=,min,(MIN(,I,1,),MIN(,I,2,),采用递归的设计策略，得到以下算法：,12/12/2025,3.一种递归求解策略,算法2.6 递归求取最大和最小元素,procedure MAXMIN(i,j,fmax,fmin),/A(1:n)是含有n个元素的数组，参数I,j是整数，1,i,jn,/,/,该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin,/,integer i,j;global n,A(1:n),case,:i=j:fmaxfminA(i)/只有一个元素,:i=j-1:if A(i)2,当n是2的幂时(n=2,k,),化简上式有，,T(n)=2T(n/2)+2,=2(2T(n/4)+2)+2,=,=2,k-1,T(2)+,=2,k-1,+2,k,-2,=3n/2-2,12/12/2025,性能分析,1）与STRAITMAXMIN算法相比，比较次数减少了25%,（3n/2-2:2n-2)。,已经达到了以,元素比较为基础,的找最大最小元素的算法,计算时间的,下界,：,2）存在的问题：,空间占用量大,有,级的递归，入栈参数：,i,j,fmax,fmin和返回地址五个值。,时间可能不比预计的理想,如果元素A(i)和A(j)的比较与i和j的比较,相差不大,时，算法MAXMIN,不可取,。,12/12/2025,假设元素的比较与i和j的比较时间相同（整型数）。又设case语句中仅需一次i和j的比较就能够确定是哪种情况。记此时MAXMIN的频率计数为C(n)，n=2,k,(k为正整数）。则有，,2 n=2,C(n)=,2C(n/2)+3 n2,化简得，,C(n)=2C(n/2)+3,=,=,5n/2-3,按照同样的假设，重新估算STRAITMAXMIN算法的比较次数为：,3(n-1)。,考虑MAXMIN算法,递归调用的开销,，此时MAXMIN算法,的效率可能还不如STRAITMAXMI算法。,12/12/2025,结论：如果A中的元素间的比较代价远比整型数,（下标）的比较,昂贵,，则分治方法将产生,一个,效率较高,的算法；,反之，可能仅得到一个,低效,的算法。,故，分治策略只能看成一个,较好的,但,并不总是成功,的算法设计指导。,12/12/2025,2.4 归并分类,1.分类问题排序,给定一n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。,分类：内排序，外排序,常见内排序方法：冒泡排序,插入排序,归并排序,快速排序,堆排序,例,输入,：（8，5，4，9）,输出：（4，5，8，9）或 （9，8，5，4）,12/12/2025,2.插入分类,算法2.7 插入分类,procedure INSERTIONSORT(A,n),/将A(1：n)中的元素按非降次序分类，n1/,A(0)-/设置初始边界值,for j2 to n do/A(1:j-1)已分类/,itemA(j);ij-1,while itemA(i)do /0ij/,A(i+1)A(i);ii-1,repeat,A(i1)item;,repeat,end INSERTIONSORT,(8,5,4,9),(,8,5,4,9),(,5,8,4,9),(,5,8,4,9),(,4,5,8,9,),(,4,5,8,9,),12/12/2025,性能分析：,最坏,情况：输入数据按非增次序排列,每次,内层while循环,执行j次（j=2,3,n)。则有，,最好,情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为,(n),12/12/2025,3.分治策略求解,基本设计思想：将原始数组A中的元素分成两个子集合：A1(1:)和A2(+1 :n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有n个元素的分类好的序列。,这样的一个分类过程称为,归并分类,。,12/12/2025,算法2.8 归并分类,procedure MERGESORT(low,high),/A(low:high)是一个全程数组，它含有high-low+1,0个待分类的元素,/,integer low,high,if lowmid then for kj to high do B(i)A(k);ii+1;repeat,else for kh to mid do B(i)A(k);ii+1;repeat,endif,for k low to high do A(k)B(k)repeat,/将已归并的集合复制到A中/,end MERGE,12/12/2025,性能分析,1)过程MERGE的归并时间与两数组元素的总数成正比,(可表示为:cn,n为元素数,c为某正常数),2)过程MERGESORT的分类时间用递推关系式表示如下:,a n=1,a是常数,T(n)=,2T(n/2)+cn n1,c是常数,化简:若n=2,k,则有,T(n)=2(2T(n/4)+cn/2)+cn,=4T(n/4)+2cn=4T(2T(n/8)+cn/4)+2cn,=,=2,k,T(1)+kcn,=an+cnlogn /k=logn/,若2,k,n2,k,+1,则有T(n)T(2,k,+1)。,所以得：,T(n)=,(nlogn),12/12/2025,归并分类示例,设A=（310，285，179，652，351，423，861，254，450，520）,1）划分过程,310，285，179，652，351，423，861，254，450，520,310，285，179，652，351,423，861，254，450，520,310，285，179,652，351,310，285,179,310,285,652,351,423，861，254,450，520,423，861,254,423,861,450,520,12/12/2025,2）归并过程,首先进入左分枝的划分与归并。首先形成的划分状态是：,（,310285,|179|652，351|423，861，254，450，520）,第一次归并：（,285，310,|179|652，351|423，861，254，450，520）,第二次归并：（,179，285，310,|652，351|423，861，254，450，520）,第三次归并：（179，285，310|,351，652,|423，861，254，450，520）,第四次归并：（,179，285，310，351，652,|423，861，254，450，520）,进入右分枝的划分与归并过程,（略）,12/12/2025,3）用树结构描述归并分类过程,12/12/2025,4.归并分类算法的改进,1）算法2.8存在的问题,递归层次太深,在MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。,在集合含有仅相当少的元素时，较深层次的递归调用使得时间,过多地消耗,在处理递归上。,元素在数组A和辅助数组B之间的频繁移动,每次归并，都要首先将A中的元素移到B中，在由B复制到A的对应位置上。,12/12/2025,2）改进措施,针对递归层次问题,采用能,在小规模集合,上有效工作的其它算法，直接对小规模集合处理。,如,INSERTIONSORT,算法,针对元素频繁移动问题,采用一个称为,链接信息数组LINK（1：n的数据结构，记录归并过程中A中的元素相对于其排序后在分类表中,位置坐标的链接关系。,LINK(i)取值于1，n，是指向A的元素的指针：在分类表中它指向下一个元素在A中的位置坐标。,12/12/2025,例：,LINK (1)(2)(3)(4)(5)(6)(7)(8),6,4,7,1,3,0,8,0,该表中含有,两个子表,，0表示表的结束。,设置,表头指针,Q和R分别指向两个子表的起始处：,Q=2，R=5；,则有，,表1：,Q(,2，4，1，6)，,经过分类后有：A(2),A(4),A(1),A(6),表2：,R(5，3，7，8)，,同样有：A(5),A(3),A(7),A(8),链接信息表在归并过程中的应用,：,将归并过程中元素在A和B之间移动的过程变成更改LINK所指示的链接关系，从而避免移动元素的本身。,分类表可以通过LINK的表头指针和读取LINK中的链接关系取得。,12/12/2025,改进后的归并分类模型,算法2.10 使用链接信息数组的归并分类模型,procedure MERGESORT1(low,high,p),/利用链接信息数组LINK(1:n)将全程数组A(low:high)按非降次序分类。LINK中值表示按分类次序给出A下标的表，并把p置于该表的开始处/,global A(low:high),LINK(low,high),if high-low+116,/当集合中的元素个数足够少(16)时，采用更有效的小规模集合上的分类,算法直接分类/,then call,INSERTSORT1,(A,LINK,low,high,p,),/算法2.7的改型/,else mid,call,MERGESORT1,(low,mid,q),/返回q表/,call,MERGESORT1,(mid+1,high,r),/返回r表/,call,MERGE1,(q,r,p),/,将表q和表r归并成表p,/,endif,end MERGESORT1,12/12/2025,算法2.11 使用链接表归并已分类的集合,procedure MERGE1(q,r,p),/q和r是全程数组LINK(1:n)中两个表的指针。归并这两个表，得到一个由p所指示的新表。此表将,A中的元素按非降次序分类。LINK(0)被定义/,global n,A(1:n),LINK(1:n),local integer i,j,k,i,q;jr;k0,/新表在LINK(0)处开始/,while i0 and j0 do,/当两表均非空时/,if A(i)A(j),/找较小的关键字/,then LINK(k)i;ki;iLINK(i),/加一个新关键字到表中/,else LINK(k)j;kj;jLINK(j),/加一个新关键字到表中/,endif,repeat,if i=0 then LINK(k)=jelse LINK(k)=i,endif,p=LINK(0),end MERGE1,12/12/2025,MERGESORT1 的调用,在初次调用时，待分类的n个元素放于A(1:n)中。,LINK(1:n)初始化为0；,初次调用：call MERGESORT1(1,n,p),p作为按分类次序给出A中元素的指示表的指针。,3）改进归并分类算法示例,设元素表：（50，10，25，30，15，70，35，55）,采用MERGESORT1对上述元素表分类（不做小规模集合的单独处理）,下表给出在每一次调用MERGESORT1结束后，LINK数组的变化情况。,12/12/2025,在上表的最后一行，p=2返回，得到链表（2，5，3，4，7，1，8，6）,即：,A(2),A(5)A(3)A(4)A(7)A(1)A(8)A(6),12/12/2025,5.以比较为基础分类的时间下界,任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为：,(nlogn),利用,二元比较树,证明。,假设参加分类的n个关键字A(1),A(2),A(n)互异。任意两个关键字的比较必导致A(i)A(j)的结果。,以二元比较树描述元素间的比较过程：,若A(i)A(j)，进入下一级的,右分支,12/12/2025,算法在,外部结点,终止。,从根到某外结点的,路径,代表某个特定输入情况下一种唯一的,分类排序序列,。,路径长度,表示生成该序列代表的分类表所需要的,比较次数。,而,最长的路径,代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。,故，以比较为基础的分类算法的,最坏情况下界,等于该算法对应的比较树的,最小高度,。,12/12/2025,由于n个关键字有,n!,种可能的排列，所以二元比较树中将有,n!,个,外部结点：,每种排列对应于某种特定输入情况下的分类情况，每个外部结点表示一种可能的分类序列。,设一棵二元比较树的所有,内结点,的级数均小于或等于,k,，则该树中最多有,2,k,个外结点。,记算法在最坏情况下所作的比较次数为,T(n)，,则有,T(n)=k：,生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1；,根据和的分析，有：,n!2,T(n),化简：,当n1时，有n!n(n-1)(n-2)()(n/2),n/2,当n4时，有 T(n)(n/2)log(n/2)(n/4)logn,故，任何以比较为基础的分类算法的最坏情况的时间下界为：,(nlogn),12/12/2025,2.5 快速分类,任何一个基于比较来确定两个元素相对位置的排序算法需要(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。,下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。,1.问题描述,分类问题,2.划分,快速分类是一种基于,划分,的分类方法；,划分,：选取待分类集合A中的某个元素t，按照与t的大小关系重,新整理A中元素，使得整理后的序列中所有在t以前出现,的元素均,小于等于,t，而所有出现在t以后的元素均,大于等,于,t。这一元素的整理过程称为,划分,（Partitioning）。元,素t称为,划分元素,。,快速分类,：通过反复地对待排序集合,进行划分,达到分类目的的分,类算法。,12/12/2025,划分过程（PARTITION）的算法描述,算法2.2 用A(m)划分集合A(m:p-1),procedure PARTITION(m,p),integer m,p,i;global A(m:p-1),vA(m);im/A(m)是划分元素/,loop,loop ii+1 until A(i)v repeat /i由左向右移/,loop pp-1 until A(p)v repeat /p由右向左移/,if ip then,call INTERCHANGE(A(i),A(p),else exit,endif,repeat,A(m)A(p)；A(p)v/划分元素在位置p/,end PARTITION,12/12/2025,注：,算法对集合A(m:p-1)进行划分。并使用待划分区间的第一个元素A(m)作为划分元素,A(p)不在划分区间内，但被定义，且A(p）,A(m)，用于限界,12/12/2025,例2.5 划分实例,(1)(2)(3)(4)(5)(6)(7)(8)(9),(10),i p,A:65,70,75 80 85 60 55 50,45,+2 9,|,A:65 45,75,80 85 60 55,50,70 +3 8,|,A:65 45 50,80,85 60,55,75 70 +4 7,|,A:65 45 50 55,85,60,80 75 70 +5 6,|,A:,65,45 50 55,60,85 80 75 70 +6 5,|,A:60 45 50 55,65,85 80 75 70 +,划分元素定位于此,交换划分元素,12/12/2025,经过一次,“划分”,后，实现了对集合元素的调整：其中一个子集合的所有元素,均小于,等于另外一个子集合的所有元素。,按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为,快速分类,。,12/12/2025,3.快速分类,通过反复使用划分过程,PARTITION,实现对集合元素分类的算法。,算法2.13 快速分类,procedure QUICKSORT(p,q),/将数组A(1:n)中的元素A(p),A(q)按递增的方式分类。,A(n+1)有定义，且假定A(n+1),+,/,integer p,q;global n,A(1:n),if pq then,j,q+1,/,进入时,，A(j)定义了划分区间p,q的,上界,，初次调用时j=n+1,call,PARTITION,(p,j),/,出口时,，j带出此次划分后划分元素所在的,坐标位置,/,call,QUICKSORT,(p,j-1),/前一子集合上递归调用,call,QUICKSORT,(j+1,q),/后一子集合上递归调用,endif,end QUICKSORT,12/12/2025,4.快速分类分析,统计的对象：元素的,比较次数,，记为：,C(n),两点假设,参加分类的n个元素各不相同PARTITION中的划分元素v是,随机,选取的（针对平均情况的分析）,随机选取划分元素,：,在划分区间m,p随机生成某一坐标：i,RANDOM(m,p-1)；,调换A(m)与A(i):vA(i);A(i)A(m);im,作用：将随机指定的划分元素的值依旧调换到A(m)位置。之后，算法主体不变，仍从A(m)开始执行划分操作。,12/12/2025,递归层次,QuickSort(1,n,),QuickSort(1,j,1,-1,),QuickSort(j,1,-1,n),QuickSort(1,j,21,-1,),QuickSort(j,21,+1,j,1,-1),QuickSort(j,1,1,j,22,-1),QuickSort(j,22,+1,n),n个元素参加划分和分类,去掉1个第一级的划分元素,n-1个元素参加划分和分类,去掉2个第二级的划分元素,n-3个元素参加划分和分类,去掉4个第三级的划分元素,第一层,第二层,第三层,设在任一级递归调用上，调用PARTITION处理的所有元素总数为,r,，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少少1：,理想情况,，第一级少1，第二级少2，第三级少4，；,最坏情况,，每次仅减少1（如集合元素已经按照递增或递减顺序排列）,12/12/2025,最坏情况分析,记,最坏情况,下的元素比较次数是,C,w,(n)；,PARTITION一次调用中的元素比较数是,p-m+1，,故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。,最坏情况下，每级递归调用的元素总数仅比上一级少1，故C,w,(n)是r由n到2的累加和。,即：C,w,(n)=,(n,2,),12/12/2025,平均情况分析,平均情况,是指集合中的元素以任一一种顺序排列，且任选所有可能的元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的,平均值,。,设调用PARTITION(m,p)时，所选取划分元素v恰好是A(m:p-1)中的第i小元素（1,ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是,A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m),m,jp。则有，,其中，,n+1是PARTITION第一次调用时所需的元素比较次数。,C,A,(0)=C,A,(1)=0,12/12/2025,化简上式可得：,C,A,(n)/(n+1)=C,A,(n-2)/(n-1)+2/n+2/(n+1),=C,A,(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1),=C,A,(1)/2+,由于,所以得，C,A,(n)2(n+1)log,e,(n+1)=,(nlogn),12/12/2025,5.快速分类算法的迭代模型,消去递归（略）,6.快速分类与归并分类比较,两者平均情况时间都是,(nlogn），平均情况下哪种快一些？,实验证明快速分类要快一些,12/12/2025,实验1,实现归并分类和快速分类算法，并比较二者的时间性能。,要求：,撰写实验报告，包括实验目的、方法、结果等，另附源程序清单,12/12/2025,2.6 选择问题,1.问题描述,给出含有n个元素表A(1:n)，要求确定其中的第k小元素。,2.设计思路,利用PARTITION过程。如果划分元素v测定在A(j)的位置上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)。此时，,若,k=j,，则A(j)即是第k小元素；否则，,若,kj,，则第k小元素将出现在A(j+1:n)中。,12/12/2025,3.利用PARTITION实现的选择算法,算法描述,算法2.15 找第k小元素,procedure SELECT(A,n,k),/在数组A(1:n)中找第k小元素，并将之放在A(k)中。/,integer n,k,m,r,j;,m,1;r,n+1;A(n+1)+,/A(n+1)被定义，并置为一大值，用于限界/,loop,/在进入循环时，1,mkrn+1/,j r,/将剩余元素的最大下标加1后置给j/,call,PARTITION,(m.j),/返回j,它使得A(j)是第j小的值/,case,:,k=j:,return,:,kj,j+1是新的下界/,endcase,repeat,end SELECT,12/12/2025,算法分析,两点假设,A中的元素,互异,随机选取,划分元素，且选择A中任一元素作为划分元,素的,概率相同,分析,每次调用PARTITION（m,j),所需的元素比较次数是,(j-m+1)。,在执行一次PARTITION后，或者找到第k小元素，或者将,在缩小的子集(A(m,k-1)或A(k+1,j)中继续查找。缩小,的子集的元素数将,至少,比上一次划分的元素数,少,1。,12/12/2025,1)最坏情况,SELECT的最坏情况时间是,(n,2,),当A中的元素已经按照,递增,的顺序排列，且,k=n,。此时，需要,n次,调用PARTITION过程，且每次返回的元素位置是子集中的第一个元素，子集合的元素数一次,仅减少,，而j值不变。,则,n次调用的时间总量是,12/12/2025,2)平均情况,设 是找A(1:n)中第k小元素的平均时间。是SELECT的平均计算时间，则有,并定义,则有：T(n)R(n),。,12/12/2025,定理2.4 SELECT的平均计算时间T,A,(n)是,(n),证明：,PARTITION和SELECT中，case语句的执行时间是,(n)。,在随机等概率选择划分元素时，首次调用PARTITION中划分元素v刚好是A中第i小元素的概率为,1/n,，1,i,n。,则，存在正常数c，c0,有，,n,2,且有，n,2,12/12/2025,令c,R(1)。利用,数学归纳法,证明，对所有n2，有R(n)4cn.,当,n=2,时，由上式得：,假设对所有得n,2nm，有R(n)4cn,当,n=m,时，有，,由于R(n)是n的非降函数，故在当m为偶数而k=m/2，或当m为奇数而k=(m+1)/2时，取得极大值。因此，,若m为偶数,，则,若m为奇数,，则,由于T,A,(n)R(n)，所以T,A,(n)4cn。,故，,T,A,(n)=,(n),12/12/2025,4.最坏情况是,(n)的选择算法,1）采用两次取中间值的规则精心选取划分元素,首先，将参加划分的n个元素分成 组，每组有r个元素(r,1)。（多余的 个元素忽略不计）,然后，对这 组每组的r个元素进行分类并找出其中间元素m,i,1i ，共得 个中间值。,之后，对这 个中间值分类，并找出其中间值mm。,将mm作为划分元素执行划分。,2）算法描述,12/12/2025,算法2.16 使用,二次取中规则,得选择算法的说明性描述,procedure SELECT2(A,k,n),/在集合A中找第k小元素，使用两次取中规则/,若nr，则采用,插入法,直接对A分类并返回第k小元素,把A分成大小为r的 个子集合，忽略多余的元素,设,M,=m1,m2,m 是 子集合的,中间值集合,v,SELECT2(M,),j,PARTITION(A，,v,),/v作为划分元素，划分后j等于划分元素所在位置的下标/,case,:,k=j,:return(v),:,kj,:设S是A(1:j-1)中元素的集合,return(SELECT2(S,k,j-1),:,else,:设R是A(j+1:n)中元素的集合,return(SELECT2(R,k-j,n-j),endcase,end SELECT2,12/12/2025,例：设 n=35,r=7。,分为,n/r=5,个元素组：,B1,，,B2,，,B3,，,B4,，,B5,；,每组有,7,个元素。,B1-B5,按照各组的,m,i,的非增次序排列。,mm=m,i,的中间值，,1,i5,由图所示有,：,mm,中间值小于等于mm的元素,大于等于mm的元素,非降次序,B,1,B,2,B,3,B,4,B,5,按照,m,i,的非降次序排列,12/12/2025,由于r个元素的,中间值,是第 小元素。则，,至少有 个m,i,小于或等于mm；,至少有,个mi大于或等于mm。,则，至少有 个元素小于或等于（或大于或等于）mm。,当,r=5,，则使用两次取中间值规则来选择v=mm，可推出，,至少有 个元素小于或等于选择元素v。,至多有 个元素大于v。,至多有 0.7n+1.2个元素小于v。,故，这样的v可,近似平均,地划分A中的n个元素。,12/12/2025,2)算法分析,记T(n)是SELECT2所需的最坏情况时