分治法——分而治之课件.ppt

《分治法——分而治之课件.ppt》由会员分享，可在线阅读，更多相关《分治法——分而治之课件.ppt（100页珍藏版）》请在三一办公上搜索。

1、2023/3/30,第四章 分治法“分”而治之,4.1 一般方法 对大规模问题的求解 利用分治法求解大规模问题,1.基本思想 分而治之方法法与软件设计的模块化方法非常相似。为解决一个大问题，可以（1）把它分解成两个或多个更小的问题；（2）分别解决每个小问题；（3）把各小问题的解答组合起来，即可得到原问题的解。小问题通常与原问题相似或同质，因而可以递归地使用分而治之策略解决。,2023/3/30,通常，子问题与原始问题“同质”,2023/3/30,例找伪币 假设16 枚金币中有一枚是伪造的，真假金币的区别仅是重量不同(伪币轻一些），利用一个没有砝码的天平作工具，找出这枚伪造的金币。,方法1：比较

2、硬币1和2的重量，有一个轻则找到；否则比较硬币3和4，依次比较下去，直到找到。最多8次比较。方法2：利用分治法。16个硬币分为两组，每组8个，比较重量，伪币在轻的一组。将轻的一组再分为两组，每组4个继续划分下去，依次每组2个，每组1个，此时找到。,2023/3/30,算法4.1 分治策略的抽象化控制procedure DANDC(p,q)global n,A(1:n);integer m,p,q;/1pqn/if SMALL(p,q)then return(G(p,q)else mDIVIDE(p,q)/pmq/return(COMBINE(DANDC(p,m),DANDC(m+1,q)end

3、ifend DANDC,注：k=2:二分是最常用的分解策略；SMALL(p,q)：布尔函数，判断输入规模q-p+1是否足够小而无需再进一步分就可求解；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.分治策略的抽象化控制,2023/3/30,DANDC的计算时间 若所分

4、成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下：g(n)n足够小 T(n)=2T(n/2)+f(n)否则 注：T(n)：表示输入规模为n的DANDC计算时间 g(n)：表示对足够小的输入规模直接求解的计算时间 f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间（该公式针对具体问题有各种不同的变形）,2023/3/30,4.2 二分检索（折半查找）,1.问题的描述 已知一个按非降次序排列的元素表a1,a2,an,判定某给定的元素x是否在该表中出现。若是，则找出x在表中的位置并返回其所在下标 若非，则返回0值。,2023/3/30,分治求解策略分析

5、：定义问题的形式描述：I=(n,a1,a2,an,x)问题分解：选取下标k，由此将I分解为3个子问题：I1=(k-1,a1,a2,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,ak+2,an,x)对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则，若xak，则只在I3中求解，对I1不用求解；I1、I3上的求解可再次采用分治方法划分后求解（递归过程）,2023/3/30,2.二分检索算法,算法4.3 二分检索procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1;highn;while lowhigh do mid

6、 case:xA(mid):low mid+1:else:jmid;return endcase repeat j0end BINSRCH,注：给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。若是，置j，使得x=A(j)若非，j=0,2023/3/30,例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中检索x=101，-14，82。执行轨迹见下表1,成功的检索,不成功的检索,成功的检索,2023/3/30,3.算法的正确性证明定理4.1 过程BINSRCH(A,n,x,j)能正确运行证明：1）在具体指定A中的数据元素及x的数据类型后，算法

7、中的所有运算都 能按要求正确运行即首先满足确定性和能行性2）终止性 算法初始部分置low1,highn 若n=0，不进入循环，j置0，算法终止 否则，进入循环，计算mid,或 x=A(mid)，j置为mid，算法终止；或xA(mid)，置lowmid+1，进入下次循环；搜索范围实际缩小 为mid+1,high，对low,mid-1区间不做进一步搜索；因low,high,mid都是整型变量，故按照上述规则，在有限步内，或找到某个mid，有A(mid)=x；或变得lowhigh，在A中没有找到任何元素等于x，算法终止。,2023/3/30,4.性能分析,1）空间特性 n+5个空间位置(n)2)时间

8、特性 区分以下情况，并进行相应的分析成功检索：所检索的x出现在A中。成功检索情况共有n种：x恰好是A中的某个元素，A中共有n个元素，故有n种可能的情况不成功检索：所检索的x不出现在A中。不成功检索情况共有n+1种：xA(n)成功/不成功检索的最好情况：执行步数最少，计算时间最短成功/不成功检索的最坏情况：执行步数最多，计算时间最长成功/不成功检索的平均情况：一般情况下的计算时间,2023/3/30,实例分析（例4.1）,频率计数特征 while循环体外语句的频率计数为1 集中考虑while循环中的x与A中元素的比较（其它运算的频率计数与之有相同的数量级）假定只需一次比较就可确定case语句控制

9、是三种情况的哪一种。查找每个元素所需的元素比较次数统计如下：,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,2023/3/30,成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/92.77次不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10=3.4次,2023/3/30,二元比较树,算法执行过程的主体是x与一系列中间元素A(mid)比较。可用一棵二元树描述这一过程，并称之为二元比较树。构造：比较树由称为

10、内结点和外结点的两种结点组成：内结点：表示一次元素比较，用圆形结点表示，存放一个mid值；代表一次成功检索；外结点：在二分检索算法中表示一种不成功检索的情况，用方形结点表示。路 径：表示一个元素的比较序列。,例4.1的二元比较树,2023/3/30,基于二元比较树的分析 若x在A中出现，则算法的执行过程在一个圆形的内结点处结束。若x不在A中出现，则算法的执行过程在一个方形的外结点处结束 外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。,例4.1的二元比较树,2023/3/30,定理4.2 若n在区域2k-1,2k)中，则对于一次成功的检索，BINSRCH至多做k次比较；对

11、于一次不成功的检索，或者做k-1次比较，或者做k次比较。证明：要点：成功检索都在内结点处结束，不成功检索都在外结点处结束 当2k-1n2k时，所有内结点在1至k级，所有外结点在第k级 或第k+1级，故：成功检索在i级终止所需要的元素比较次数是i 不成功检索在i级外部结点终止的元素比较次数是i-1,2023/3/30,BINSRCH计算复杂度的理论分析,1）不成功检索的最好、最坏和平均情况的计算时间均为 外结点处在最末的两级上；2）最好情况下的成功检索的计算时间为 最坏情况下的成功检索的计算时间为,2023/3/30,3）平均情况下的成功检索的计算时间分析 利用外部结点和内部结点到根距离和之间的

12、关系进行推导：记，由根到所有内结点的距离之和称为内部路径长度，记为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)=,2023/3/30,4.以比较为基础检索的时间下界,问题：设n个元素的数组A(1:n)有A(1)A(2)A(n)。检索一给定元素x是否在A中出现。定理4.2给出了二分检索算法的时间下界，是否预计还存在有以元素

13、比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有更低的数量级?以比较为基础的算法：假定算法中只允许进行元素间的比较，而不允许对它们实施其它运算。,2023/3/30,注：每个内结点表示一次元素的比较。每棵比较树中恰好含有n个内结点，分别与n个不同i值相对应；每个外结点对应一次不成功的检索，并恰好又n+1个外结点对应于n+1中不成功检索的情况。,任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。,2023/3/30,以比较为基础的有序检索问题最坏情况的时间下界定理4.3 设A(1:n)含有 n(n1)个不同的元素，排序为A(1)A(2)A(n)。又设用以比较为

14、基础的算法去判断是否，则这样的任何算法在最坏情况下所需的最小比较次数FIND(n)有：,证明：从模拟求解检索问题算法的比较树可知，FIND(n)不大于树中由根到一个叶子的最长路径的距离。而所有树中必定有n个内结点与x在A中的n中可能的出现相对应。如果一棵二元树的所有内结点所在的级数小于或等于k，则最多有2k-1个内结点。故n2k-1,即,2023/3/30,任何一种以比较为基础的算法，在最坏情况下的计算时间都不低于(logn)。因此，不可能存在最坏情况比二分检索数量级还低的算法。二分检索是解决检索问题的最优的最坏情况算法。,2023/3/30,4.3 找最大和最小元素,问题描述：给定含有n个元

15、素的集合，在其中找出最大和最小元素。,2023/3/30,1.直接找最大和最小元素算法4.5 直接找最大和最小元素procedure STRAITMAXMIN(A,n,max,min)/将A中的最大值置于max，最小值置于min/Integer i,n maxminA(1)for i2 to n do if A(i)max then maxA(i)endif if A(i)min then minA(i)endif repeatend STRAITMAXMIN,算法的性能：只考虑算法中的比较运算，以此代表算法的执行特征；该算法最好、最坏、平均情况下均需要做2(n-1)次元素比较,2023/3/

16、30,STRAITMAXMIN算法的一种简单改进形式:procedure STRAITMAXMIN1(A,n,max,min)integer i,n maxminA(1)for i2 to n do if A(i)max then maxA(i)endif else if A(i)min then minA(i)endif repeatend STRAITMAXMIN1这使得，最好情况：按递增次序排列，元素比较次数为n-1次最坏情况：按递减次序排列，元素比较次数为2(n-1)次平均情况：元素比较次数为3(n-1)/2次,2023/3/30,2.分治求解策略 记问题的一个实例为：I=(n,A(1

17、),A(n)采用二分法将I分成两个子集合处理 I1=(,A(1),，A()，和 I2=(n-,A(+1),，A(n)则有，MAX(I)=max(MAX(I1),MAX(I2)MIN(I)=min(MIN(I1),MIN(I2)采用递归的设计策略，得到以下算法：,2023/3/30,3.一种递归求解策略,算法4.6 递归求取最大和最小元素procedure MAXMIN(i,j,fmax,fmin)/A(1:n)是含有n个元素的数组，参数I,j是整数，1i,jn/该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin/integer i,j;global n,A(1:n)case:i=

18、j:fmaxfminA(i)/只有一个元素:i=j-1:if A(i)A(j)then fmaxA(j);fminA(i)else fmaxA(i);fminA(j)/两个元素的情况 endif:else:mid/取中 call MAXMIN(i,mid,gmax,gmin)call MAXMIN(mid+1,j,hmax,hmin)fmaxmax(gmax,hmax);fminmin(gmin,hmin)end case end MAXMIN,2023/3/30,例：在A(1:9)=(22,13,-5,-8,15,60,17,31,47)上执行算法4.6,每个结点内的值分别是：i,j,fma

19、x,fmin,递归调用,递归调用分解过程,递归调用的返回,2023/3/30,性能分析(T(n)表示元素比较数）0 n=1 T(n)=1 n=2 n2当n是2的幂时(n=2k),化简上式有，T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=2k-1T(2)+=2k-1+2k-2=3n/2-2,2023/3/30,性能分析1）与STRAITMAXMIN算法相比，比较次数减少了25%（3n/2-2:2n-2)。已经达到了以元素比较为基础的找最大最小元素的算法 计算时间的下界：2）存在的问题：空间占用量大 有 级的递归，入栈参数：i,j,fmax,fmin和返回地址五个值。时间可能不比预计

20、的理想 如果元素A(i)和A(j)的比较与i和j的比较相差不大时，算法MAXMIN不可取。,2023/3/30,假设元素的比较与i和j的比较时间相同（整型数）。又设case语句中仅需一次i和j的比较就能够确定是哪种情况。记此时MAXMIN的频率计数为C(n)，n=2k(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算法。,2023/3/30,结论：

21、如果A中的元素间的比较代价远比整型数（下标）的比较昂贵，则分治方法将产生 一个效率较高的算法；反之，可能仅得到一个低效的算法。故，分治策略只能看成一个较好的但并不总是成功 的算法设计指导。,2023/3/30,思考题：最大子段和问题,求数列的最大子段和。给定n个元素的整数列(可能为负整数)a1，a2，an，求形如ai，ai+1，aj，i，j=1，2，n，i=j的子段，使其和为最大。例如，当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2),max_sum=20，best_i=2，best_j=4,2023/3/30,若用一般的二分法解决该实例？,分解为两组(-2,1

22、1,-4)和(13,-5,-2),11,13,不独立，子问题中间有公共子问题,2023/3/30,对重叠子问题专门处理,“三”分治,情形1,情形2,情形3,将a1.n分为长度相等的2段a1.(n/2)和a(n/2)+1.n,分别求这2段最大子段和,则a1.n最大子段和有3种情形:1)a1.n的最大子段和与a1.(n/2)的最大子段和相同；2)a1.n的最大子段和与a(n/2)+1.n的最大字段和相同;3)a1.n的最大字段和为ai.j,且1i(n/2),(n/2)+1jn。情况1)和情况2)可分别递归求得。对于情况3）,a(n/2)与a(n/2)+1一定在最大子段中。因此,可以计算出ai.(n

23、/2)最大值s1和a(n/2)+1.j最大值s2。则s1+s2即为情况3)时最优值。,2023/3/30,“三”分治,情形1,情形2,情形3,对分解得到的左右子段，求左右子段内部的最大子段和；左子段中满足以下条件的最大的子段和s1：以任何位置i开始，结尾处n/2结束；右子段中满足以下条件的最大的子段和s2：以起始位置n/2+1开始，任何位置j结束；,原问题最大子段和是左右子段内最大和与两个子段最大值求和s1+s2中的大者。,2023/3/30,4.4 归并分类,1.分类问题排序 给定一n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。分类：内排序，外排序 常见内排序方法：冒泡排序

24、 插入排序 归并排序 快速排序 堆排序,例 输入：（8，5，4，9）输出：（4，5，8，9）或（9，8，5，4）,2023/3/30,2.插入分类 算法4.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(i+1)item;repeat end INSERTIONSORT,(8,5,4,9)(8,5,4,9)(5,8,4,9)(5

25、,8,4,9)(4,5,8,9)(4,5,8,9),2023/3/30,性能分析：最坏情况：输入数据按非增次序排列,每次内层while循环执行j次（j=2,3,n)。则有，最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为(n),2023/3/30,3.分治策略求解 基本设计思想：将原始数组A中的元素分成两个子集合：A1(1:)和A2(+1:n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有n个元素的分类好的序列。这样的一个分类过程称为归并分类。,2023/3/30,算法4.8 归并分类 procedure MERGESORT(low,high

26、)/A(low:high)是一个全程数组，它含有high-low+10个待分类的元素/integer low,high if lowhigh then mid/计算中分点/call MERGESORT(low,mid)/在第一个子集合上分类(递归)/call MERGESORT(mid+1,high)/在第二个子集合上分类(递归)/call MERGE(low,mid,high)/归并已分类的两子集合/endif end MERGESORT,2023/3/30,算法4.9 使用辅助数组归并两个已分类的集合 procedure MERGE(low,mid,high)/A(low,high)是一个

27、全程数组,它含有两个放在A(low,mid)和A(mid+1,high)中的已分 类的子集合.目标是将这两个已分类的集合归并成一个集合，并存放到A(low,high)中/integer h,I,j,k,low,mid,high;/lowmidhigh/global A(low,high);local B(low,high)hlow;ilow;jmid+1;while hmid and jhigh do/当两个集合都没有取尽时,将较小的元素先存放到B中/if A(h)A(j)then B(i)A(h);hh+1/如果前一个数组中的元素较小/else B(i)A(j);jj+1/如果后一个数组中的

28、元素较小/endif repeat/处理尚有剩余元素的集合/if hmid 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,2023/3/30,性能分析1)过程MERGE的归并时间与两数组元素的总数成正比(可表示为:cn,n为元素数,c为某正常数)2)过程MERGESORT的分类时间用递推关系式表示如下:a n=1,a是常数 T(n)=2T(

29、n/2)+cn n1,c是常数化简:若n=2k,则有,T(n)=2(2T(n/4)+cn/2)+cn=4T(n/4)+2cn=4T(2T(n/8)+cn/4)+2cn=2kT(1)+kcn=an+cnlogn/k=logn/若2kn2k+1,则有T(n)T(2k+1)。所以得：T(n)=(nlogn),2023/3/30,归并分类示例,设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,

30、310，285，179,652，351,310，285,179,310,285,652,351,423，861，254,450，520,423，861,254,423,861,450,520,2023/3/30,2）归并过程首先进入左分枝的划分与归并。首先形成的划分状态是：（310|285|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|4

31、23，861，254，450，520）第四次归并：（179，285，310，351，652|423，861，254，450，520）进入右分枝的划分与归并过程（略）,2023/3/30,3）用树结构描述归并分类过程,2023/3/30,4.归并分类算法的改进,1）算法4.8存在的问题 递归层次太深 在MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。在集合含有仅相当少的元素时，较深层次的递归调用使得时间过多地消耗在处理递归上。元素在数组A和辅助数组B之间的频繁移动 每次归并，都要首先将A中的元素移到B中，在由B复制到A的对

32、应位置上。,2023/3/30,2）改进措施 针对递归层次问题 采用能在小规模集合上有效工作的其它算法，直接对小规模集合处理。如INSERTIONSORT算法 针对元素频繁移动问题 采用一个称为链接信息数组LINK（1：n）的数据结构，记录归并过程中A中的元素相对于其排序后在分类表中位置坐标的链接关系。LINK(i)取值于1，n，是指向A的元素的指针：在分类表中它指向下一个元素在A中的位置坐标。,2023/3/30,例：LINK(1)(2)(3)(4)(5)(6)(7)(8)6 4 7 1 3 0 8 0该表中含有两个子表，0表示表的结束。设置表头指针Q和R分别指向两个子表的起始处：Q=2，R

33、=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中的链接关系取得。,2023/3/30,改进后的归并分类模型,算法4.10 使用链接信息数组的归并分类模型procedure MERGESORT1(low,high,p)/利用链接信息数组LINK(1:n)将全程数组A(low:high)按非降次序分类。LINK中值表示按分

34、类次序给出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/endifend MERGESORT1,2023/3/30,

35、算法4.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 iq;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)/加一个新

36、关键字到表中/endif repeat if i=0 then LINK(k)=j else LINK(k)=i endif p=LINK(0)end MERGE1,2023/3/30,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结束后，LI

37、NK数组的变化情况。,2023/3/30,在上表的最后一行，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),2023/3/30,5.以比较为基础分类的时间下界,任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为：(nlogn)利用二元比较树证明。假设参加分类的n个关键字A(1),A(2),A(n)互异。任意两个关键字的比较必导致A(i)A(j)的结果。以二元比较树描述元素间的比较过程：若A(i)A(j)，进入下一级的右分支,2023/3/30,算法在外部结点终止。从根到某外结点的路径代表某个特定输入情况下一种

38、唯一的分类排序序列。路径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。故，以比较为基础的分类算法的最坏情况下界等于该算法对应的比较树的最小高度。,2023/3/30,由于n个关键字有n!种可能的排列，所以二元比较树中将有n!个外部结点：每种排列对应于某种特定输入情况下的分类情况，每个外部结点表示一种可能的分类序列。设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个外结点。记算法在最坏情况下所作的比较次数为T(n)，则有T(n)=k：生成外结点所代表的分类序列所需的比较次数等于该外结

39、点所在的级数-1；根据和的分析，有：n!2T(n)化简：当n1时，有n!n(n-1)(n-2)()(n/2)n/2 当n4时，有 T(n)(n/2)log(n/2)(n/4)logn 故，任何以比较为基础的分类算法的最坏情况的时间下界为：(nlogn),2023/3/30,4.5 快速分类,任何一个基于比较来确定两个元素相对位置的排序算法需要(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。1

40、.问题描述 分类问题2.划分 快速分类是一种基于划分的分类方法；划分：选取待分类集合A中的某个元素t，按照与t的大小关系重 新整理A中元素，使得整理后的序列中所有在t以前出现 的元素均小于等于t，而所有出现在t以后的元素均大于等 于t。这一元素的整理过程称为划分（Partitioning）。元 素t称为划分元素。快速分类：通过反复地对待排序集合进行划分达到分类目的的分 类算法。,2023/3/30,划分过程（PARTITION）的算法描述,算法4.12 用A(m)划分集合A(m:p-1)procedure PARTITION(m,p)integer m,p,i;global A(m:p-1)v

41、A(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,2023/3/30,注：算法对集合A(m:p-1)进行划分。并使用待划分区间的第一个元素A(m)作为划分元素 A(p)不在划分区间内，但被定义，且A(p）A(m)，用于限界,2023/3/30,例2.5 划分实例(

42、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+,划分元素定位于此,交换划分元素,2023/3/30,经过一次“划分”后，实现了对集合元素的调整：其中一个子集合的所有元素均小于等于另外一个子集

43、合的所有元素。按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类。,2023/3/30,3.快速分类 通过反复使用划分过程PARTITION实现对集合元素分类的算法。算法4.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 jq+1/进入时，A(j)定义了划分区间p,q的上界，初次调用时j=n+1 call PAR

44、TITION(p,j)/出口时，j带出此次划分后划分元素所在的坐标位置/call QUICKSORT(p,j-1)/前一子集合上递归调用 call QUICKSORT(j+1,q)/后一子集合上递归调用 endif end QUICKSORT,2023/3/30,4.快速分类分析统计的对象：元素的比较次数，记为：C(n)两点假设 参加分类的n个元素各不相同 PARTITION中的划分元素v是随机选取的（针对平均情况的分析）随机选取划分元素：在划分区间m,p随机生成某一坐标：iRANDOM(m,p-1)；调换A(m)与A(i):vA(i);A(i)A(m);im作用：将随机指定的划分元素的值依旧

45、调换到A(m)位置。之后，算法主体不变，仍从A(m)开始执行划分操作。,2023/3/30,递归层次,QuickSort(1,n),QuickSort(1,j1-1),QuickSort(j1+1,n),QuickSort(1,j21-1),QuickSort(j21+1,j1-1),QuickSort(j1-1,j22-1),QuickSort(j22+1,n),n个元素参加划分和分类,去掉1个第一级的划分元素,n-1个元素参加划分和分类,去掉2个第二级的划分元素,n-3个元素参加划分和分类,去掉4个第三级的划分元素,第一层,第二层,第三层,设在任一级递归调用上，调用PARTITION处理的

46、所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少少1：理想情况，第一级少1，第二级少2，第三级少4，；最坏情况，每次仅减少1（如集合元素已经按照递增或递减顺序排列）,2023/3/30,最坏情况分析 记最坏情况下的元素比较次数是Cw(n)；PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。即：Cw(n)=(n2),2023/3/30,平均情况分析 平均情况是指集合中的元素以任一一种顺序排列，且任选

47、所有可能的元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。设调用PARTITION(m,p)时，所选取划分元素v恰好是A(m:p-1)中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m),mjp。则有，其中，n+1是PARTITION第一次调用时所需的元素比较次数。CA(0)=CA(1)=0,2023/3/30,化简上式可得：CA(n)/(n+1)=CA(n-2)/(n-1)+2/n+2/(n+1)=CA(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1)=

48、CA(1)/2+由于所以得，CA(n)2(n+1)loge(n+1)=(nlogn),2023/3/30,5.快速分类算法的迭代模型,消去递归（略）6.快速分类与归并分类比较两者平均情况时间都是(nlogn），平均情况下哪种快一些？实验证明快速分类要快一些,2023/3/30,4.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(

49、j+1:n)中。,2023/3/30,举例,在四人中找第二高（即第三矮）吴宗宪，曾志伟，古天乐，周润发,2023/3/30,3.利用PARTITION实现的选择算法,算法描述 算法4.15 找第k小元素 procedure SELECT(A,n,k)/在数组A(1:n)中找第k小元素，并将之放在A(k)中。/integer n,k,m,r,j;m1;r n+1;A(n+1)+/A(n+1)被定义，并置为一大值，用于限界/loop/在进入循环时，1mkrn+1/j r/将剩余元素的最大下标加1后置给j/call PARTITION(m，j)/返回j,它使得A(j)是第j小的值/case:k=j:

50、return:kj,j+1是新的下界/endcase repeat end SELECT,2023/3/30,算法分析 两点假设 A中的元素互异 随机选取划分元素，且选择A中任一元素作为划分元 素的概率相同 分析 每次调用PARTITION（m,j),所需的元素比较次数是(j-m+1)。在执行一次PARTITION后，或者找到第k小元素，或者将 在缩小的子集(A(m,k-1)或A(k+1,j)中继续查找。缩小 的子集的元素数将至少比上一次划分的元素数少1。,2023/3/30,1)最坏情况 SELECT的最坏情况时间是(n2)当A中的元素已经按照递增的顺序排列，且k=n。此时，需要n次调用PA