第4章 分治法.ppt

《第4章 分治法.ppt》由会员分享，可在线阅读，更多相关《第4章 分治法.ppt（97页珍藏版）》请在麦多课文档分享上搜索。

1、第4章 分治法, “分”而治之,主要内容,一般方法 二分检索 找最大和最小元素 归并分类 快速分类 选择问题 斯特拉森矩阵乘法,对大规模问题的求解 利用分治法求解大规模问题,1.基本思想分而治之方法与软件设计的模块化方法非常相似。为解决一个大问题，可以（1）把它分解成两个或多个更小的问题；（2）分别解决每个小问题；（3）把各小问题的解答组合起来，即可得到原问题的解。小问题通常与原问题相似或同质 ，因而可以递归地使用分而治之策略解决。,3.1 一般方法,通常，子问题与原始问题“同质”,例1 找伪币 假设16 枚金币中有一枚是伪造的，真假金币的区别仅是重量不同，利用一个没有砝码的天平作工具，找出这

2、枚伪造的金币。,例2 金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新金块快加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重，如果有新的金块周期性的加入袋中，则每个月都必须找出最重和最轻的金块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。问题的分解策略有多种。,例3 矩阵乘法两个nn阶的矩阵A与B的乘积是另一个nn阶矩阵C,C的元素可表示为：,其时间复杂度为O(n3)。可以采用矩阵分块乘法降低时间复杂度。先将A、B分别

3、分割为4个n/2n/2的矩阵，然后组合。,分治法自然导致了递归算法的使用。在许多例子里，这些递归算法在递归程序中得到了很好的运用。,算法3.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)endif end DANDC,注： k=2: 二分是最常用的分解策略； SMALL(p,q)：布尔函数，判断输入规模q-p+1是

4、否足够小而无需再进一步分就可求解； 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. 分治策略的抽象化控制,DANDC的计算时间若所分成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下：g(n) n足够小T(n) = 2T(n/2) +

5、 f(n) 否则,注：T(n)：表示输入规模为n的DANDC计算时间g(n)：表示对足够小的输入规模直接求解的计算时间f(n)：表示COMBINE对两个子区间的子结果进行合并的时间（该公式针对具体问题有各种不同的变形）,分治法的另一种模型表示,proc dividandconquer(n)if n=n0 then g(n)else divid n into small suninstancesn1 n2 n3nkfor i=1 to k doyi=dividandconquer(ni)return merge(y1yk) end dividandconquer,T(n)= G(n) nn0 其

6、中，f(n)是合并各部分解的时间，k,m均为常数,进一步思考,n0选择多大合适？ 原问题应该分解成几个子问题？ 大量实践得出子问题的规模大致相当分治的效率较好。 一般进行2分法。,3.2 二分检索（折半查找）,1. 问题的描述已知一个按非降次序排列的元素表a1, a2, ,an,判定某给定的元素x是否在该表中出现。若是，则找出x在表中的位置并返回其所在下标若非，则返回0值。,分治求解策略分析：定义问题的形式描述：I=(n, a1, a2, ,an,x)问题分解：选取下标k，由此将I分解为3个子问题： I1=(k-1, a1, a2, ,ak-1,x)I2=(1, ak,x)I3=(n-k, a

7、k+1, ak+2, ,an,x)对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则，若xak，则只在I3中求解，对I1不用求解；I1 、I3上的求解可再次采用分治方法划分后求解（递归过程）k的不同选择策略导致不同的检索算法：二分检索，Fibonacci检索，线性插值检索，随机检索。,2. 二分检索算法,算法3.3 二分检索 procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1; highn;while lowhigh domid case:xA(mid):low mid+1 :else:jmid;returnendcaser

8、epeatj 0 end NIBSRCH,注：给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。 若是，置j，使得x=A(j) 若非，j=0,例3.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中检索x=101，-14，82。执行轨迹见下表1,成功的检索,不成功的检索,成功的检索,3. 算法的正确性证明 定理3.1 过程BINSRCH(A,n,x,j)能正确运行 证明： 1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都能按要求正确运行即首先满足确定性和能行性 2）终止性算法初始部分置low1, highn 若n=0，不进入循环，

9、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，算法终止。,4. 性能分析,1）空间特性n+5个空间位置(n) 2) 时间特性区分以下情况，并进行相应的分析 成功检索：所检索的x出现在A中。 成功检索情况共有n种：x恰好是A中的某个元素，A中共有n个元素

10、，故有n种可能的情况 不成功检索：所检索的x不出现在A中。不成功检索情况共有n+1种：xA(n) 成功/不成功检索的最好情况：执行步数最少，计算时间最短 成功/不成功检索的最坏情况：执行步数最多，计算时间最长 成功/不成功检索的平均情况：一般情况下的计算时间,实例分析（例3.1）,频率计数特征while循环体外语句的频率计数为1集中考虑while循环中的x与A中元素的比较（其它运算的频率计数与之有相同的数量级）假定只需一次比较就可确定case语句是三种情况的哪一种。查找每个元素所需的元素比较次数如下：,A 元素 -15 -6 0 7 9 23 54 82 101 成功检索 3 2 3 4 1

11、3 2 3 4 比较次数 不成功检索3 3 3 4 4 3 3 3 4 4 比较次数,9个元素情况下： 成功检索最好：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次,二元比较树,算法执行过程的主体是x与一系列中间元素A(mid)比较。可用一棵二元树描述这一过程，称之为二元比较树。 构造：比较树由内结点和外结点的两种结点组成： 内结点：表示一次元素比较，用圆形结点表示，存放一个mid值；代表一次成功检索； 外结点：表示一种不成功检索的情况，用方形结点表示。 路径:表示一个

12、元素的比较序列。,例3.1的二元比较树,基于二元比较树的分析若x在A中出现，则算法的执行过程在一个圆形的内结点处结束。若x不在A中出现，则算法的执行过程在一个方形的外结点处结束外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。,例3.1的二元比较树,6,定理3.2 若n在区域2k-1,2k)中，则对于一次成功的检索，BINSRCH至多做k次比较；对于一次不成功的检索，或者做k-1次比较，或者做k次比较。 证明：成功检索都在内结点处结束，不成功检索都在外结点处结束当2k-1n2k时，所有内结点在1至k级，所有外结点在第k级 或第k+1级，故：成功检索在i级终止所需要的元素比较

13、次数是i不成功检索在i级外部结点终止的元素比较次数是i-1,BINSRCH计算复杂度的理论分析,1）不成功检索的最好、最坏和平均情况的计算时间均为 外结点处在最末的两级上；2）最好情况下的成功检索的计算时间为最坏情况下的成功检索的计算时间为,3）平均情况下的成功检索的计算时间分析利用外部结点和内部结点到根距离和之间的关系进行推导：记，由根到所有内结点的距离之和称为内部路径长度，记为I；由根到所有外部结点的距离之和称为外部路径长度，记为E。则有，E=I+2n 引入记号U(n) ，S(n)。U(n)是平均情况下不成功检索的计算时间，(外结点的比较次数是根到该结点的路径长度)，则U(n) = E/(

14、n+1) S(n)是平均情况下成功检索的计算时间，（内结点表示元素比较次数是由跟到该结点的路径长度+1）则S(n) = (I+n)/n=I/n+1,利用上述公式，可有: S(n) = (1+1/n)U(n) -1当n,S(n) U(n) ，而U(n) =所以 S(n) =,1,2,3,5. 以比较为基础检索的时间下界,问题：设n个元素的数组A(1:n)有A(1) A(2) A(n)。检索一给定元素x是否在A中出现。定理3.2给出了二分检索算法的时间下界。能否预计还存在有以元素比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有更低的数量级?以比较为基础的算法：假定算法中只允许

15、进行元素间的比较，而不允许对它们实施其它运算。,注：每个内结点表示一次元素的比较。每棵比较树中恰好含有n个内结点，分别与n个不同i值相对应；每个外结点对应一次不成功的检索，并恰好有n+1个外结点对应于n+1中不成功检索的情况。,任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。,以比较为基础的有序检索问题最坏情况的时间下界 定理3.3 设A(1:n)含有 n(n1)个不同的元素，排序为A(1) A(2) A(n)。又设用以比较为基础的算法去判断是否 ，则这样的任何算法在最坏情况下所需的最小比较次数FIND(n)有：,证明：从模拟求解检索问题算法的比较树可知，FIND(n)不大于树

16、中由根到一个叶子的最长路经的距离。而所有树中必定有n个内结点与x在A中的n中可能的出现相对应。如果一棵二元树的所有内结点所在的级数小于或等于k，则最多有2k-1个内结点。故n2k-1,即,任何一种以比较为基础的算法，在最坏情况下的计算时间都不低于(logn)。因此， 不可能存在最坏情况比二分检索数量级还低的算法。 二分检索是解决检索问题的最优的最坏情况算法。,3.3 找最大和最小元素,问题描述：给定含有n个元素的集合，在其中找出最大和最小元素。,1. 直接找最大和最小元素 算法3.5 直接找最大和最小元素 procedure STRAITMAXMIN(A,n,max,min) /将A中的最大值

17、置于max，最小值置于min/Integer i,nmaxminA(1)for i2 to n doif A(i) max thenmaxA(i)endifif A(i) min then minA(i)endifrepeat end STRAITMAXMIN,算法的性能： 只考虑算法中的比较运算，以此代表算法的执行特征； 该算法最好、最坏、平均情况下均需要做2（n-1)次元素比较,STRAITMAXMIN算法的一种简单改进形式: procedure STRAITMAXMIN1(A,n,max,min)integer i,nmaxminA(1)for i2 to n doif A(i) max

18、 then maxA(i) endifelse if A(i) min then minA(i) endifrepeat end STRAITMAXMIN1 这使得， 最好情况：按递增次序排列，元素比较次数为n-1次 最坏情况：按递减次序排列，元素比较次数为2(n-1)次 平均情况：元素比较次数为3(n-1)/2次,2. 分治求解策略记问题的一个实例为：I = (n, A(1), , A(n)采用二分法将I分成两个子集合处理I1 = ( , A(1), ，A( )，和I2 = (n- , A( +1), ， A(n)则有，MAX(I) = max(MAX(I1),MAX(I2)MIN(I) =

19、 min(MIN(I1),MIN(I2)采用递归的设计策略，得到以下算法：,3. 一种递归求解策略,算法3.6 递归求取最大和最小元素 procedure MAXMIN(i,j,fmax,fmin)/A(1:n)是含有n个元素的数组，参数i,j是整数，1i,jn /该过程把A(i:n)中的最大和最小元素分别赋给max和min /integer i,j;global n,A(1:n)case:i=j: fmaxfminA(i) /只有一个元素:i=j-1:if A(i)A(j) then fmaxA(j);fminA(i)else fmaxA(i);fminA(j) /两个元素的情况endif:

20、else: mid /取中call MAXMIN(i,mid,gmax,gmin)call MAXMIN(mid +1,j,hmax,hmin)fmaxmax(gmax,hmax); fminmin(gmin,hmin)end caseend MAXMIN,例：在A(1:9) = (22,13,-5,-8,15,60,17,31,47)上执行算法3.6,每个结点内的值分别是： i, j, fmax, fmin,递归调用,递归调用分解过程,递归调用的返回,性能分析,当n是2的幂时(n=2k),化简上式有:,若2k-1n2k,+2,性能分析 1）与STRAITMAXMIN算法相比，比较次数减少了2

21、5%（3n/2-2 : 2n-2)。已经达到了以元素比较为基础的找最大最小元素的算法计算时间的下界： 2）存在的问题： 空间占用量大 有 级的递归，入栈参数： i, j, fmax, fmin和返回地址五个值。时间可能不比预计的理想如果元素A(i)和A(j)的比较与i和j的比较相差不大时，算法MAXMIN不可取。,假设元素的比较与i和j的比较时间相同（整型数）。又设case语句中仅需一次i和j的比较就能够确定是哪种情况。记此时MAXMIN的频率计数为C(n)，n=2k (k为正整数）。则有，2 n=2C(n) = 2C(n/2)+3 n2化简得，C(n) = 2C(n/2) + 3 = = 5

22、n/2 -3按照同样的假设，重新估算STRAITMAXMIN算法的比较次数为：3(n-1)。考虑MAXMIN算法递归调用的开销，此时MAXMIN算法的效率可能还不如STRAITMAXMI算法。,结论：如果A中的元素间的比较代价远比整型数（下标）的比较昂贵，则分治方法将产生一个效率较高的算法；反之，可能仅得到一个低效的算法。故，分治策略只能看成一个较好的但并不总是成功的算法设计指导。,3.4 归并分类,1. 分类问题排序给定一n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。分类：内排序，外排序 内排序：以比较为基础（键排序）、位排序、映射排序常见内排序方法：冒泡排序插入排序归并排

23、序快速排序堆排序,2. 插入分类,算法3.7 插入分类 procedure INSERTIONSORT(A,n)/将A(1：n)中的元素按非降次序分类，n1for j2 to n do /A(1:j-1)已分类itemA(j); /岗哨ij-1while itemA(i) do /0ij A(i+1)A(i); ii-1repeatA(i+1) item;repeatend INSERTIONSORT,基本思想： 将A(j)插入到已排序的序列A(1)A(j-1)中。 从j-1向前找到位置i将其插入,性能分析：最坏情况：输入数据按非增次序排列,每次内层while循环执行j次（j=2,3, n)。

24、则有：,最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为(n)。,3.分治策略求解,基本设计思路： 若n为1，算法结束； 否则，将这一元素集合分割成两个或更多个子集合，对每个子集合分别分类，然后将分好类的子集合归并为一个集合。插入分类、选择分类、可以看成特殊的情况：分割方案将n个元素分成两个极不平衡的集合A和B。A含有n-1个元素，B含有1个元素。性能最佳的分割方式将原始数据分割成两个元素个数近似相等的子集合：A1(1: n/2 )和A2(n/2 +1 :n)。这就是2路归并分类。,算法3.8 递归形式的2路归并分类 procedure MERGESORT(low

25、,high)/A(low:high)是一个全程数组，它含有high-low+10个待分类的元素/integer low,highif lowhigh thenmid(low+high)/2 call MERGESORT(low,mid) /在第一个子集合上分类(递归)/call MERGESORT(mid+1,high) /在第二个子集合上分类(递归)/call MERGE(low,mid,high) /归并已分类的两子集合/endifend MERGESORT,基本思路： 把A(1)A(n)分成I1: A(1)A(n/2)和I2:A(n/2+1)A(n)两个子列. 对I1、I2两个子列进行单

26、独排序。 将已分类的两序列归并成一个含有n个元素的序列。,算法3.9 使用辅助数组归并两个已分类的集合procedure MERGE(low,mid,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 /如果后一个数

27、组中的元素较小/endifrepeat /处理尚有剩余元素的集合/if hmid then for kj to high do B(i) A(k);ii+1; else for kh to mid do B(i) A(k);ii+1;endiffor k low to high do A(k) B(k) repeat/将已归并的集合复制到A/end MERGE,性能分析 1) 过程MERGE的归并时间与两数组元素的总数成正比(可表示为:cn, n为元素数,c为某正常数) 2) 过程MERGESORT的分类时间用递推关系式表示如下:,化简: 若n=2k,则有,T(n) =2(2T(n/4)+cn

28、/2)+cn = 4T(n/4) + 2cn =4T(2T(n/8) +cn/4) + 2cn= =2kT(1)+kcn=an+cnlogn /k=logn/若2kn 2k+1,则有T(n)T(2k+1)。 所以得：T(n) = (nlogn) 最好情况、最坏情况和平均情况的时间复杂度相同。,归并分类示例,设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,65

29、2，351,310，285,179,310,285,652,351,423，861，254,450，520,423，861,254,423,861,450,520,2）归并过程 首先进入左分枝的划分与归并。首先形成的划分状态是： 归并（310 | 285 | 179 | 652，351 | 423，861，254，450，520） 第1次（285，310 | 179 | 652，351 | 423，861，254，450，520） 第2次（179，285，310 | 652，351 | 423，861，254，450，520） 第3次（179，285，310 |351，652 | 423，86

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

31、模集合上有效工作的其它算法，直接对小规模集合处理。如INSERTIONSORT算法针对元素频繁移动问题采用一个称为链接信息数组LINK（1：n）的数据结构，记录归并过程中A中的元素相对于其排序后在分类表中位置坐标的链接关系。LINK(i)取值于1，n，是指向A的元素的指针：在分类表中它指向下一个元素在A中的位置坐标。,例：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

32、(6) 表2：R(5，3，7，8)，同样有：A(5)A(3) A(7) A(8)链接信息表在归并过程中的应用：将归并过程中元素在A和B之间移动的过程变成更改LINK所指示的链接关系，从而避免移动元素的本身。分类表可以通过LINK的表头指针和读取LINK中的链接关系取得。,改进后的归并分类模型,算法3.10 使用链接信息数组的归并分类模型 procedure MERGESORT1(low,high,p)/利用链接信息数组LINK(1:n)将全程数组A(low:high)按非降次序分类。LINK中值表示按分类次序给出A下标的表，并把p置于该表的开始处/ global A(low:high),LIN

33、K(low,high) if high-low+116 /当集合中的元素个数足够少(16)时，采用更有效的小规模集合上的分类算法直接分类/then call INSERTSORT1(A,LINK,low,high,p) /算法3.7的改型/else mid(low+high)/2 call MERGESORT1(low,mid,q) /返回q表/call MERGESORT1(mid+1,high,r) /返回r表/call MERGE1(q,r,p) /将表q和表r归并成表p/ endif end MERGESORT1,7,算法3.11 使用链接表归并已分类的集合procedure MERG

34、E1(q,r,p)/q和r是全程数组LINK(1:n)中两个表的指针。归并这两个表，得到一个由p所指示的新表。此表将A中的元素按非降次序分类。LINK(0)被定义/global n,A(1:n),LINK(1:n)local integer i,j,kiq;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) /加一个新关键字到表中/endifrepeatif i=0 then

35、 LINK(k) = jelse LINK(k) = iendif P link(0);end MERGE1,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数组的变化情况。,p=2返回，得到链表（2，5，3，4，7，1，8，6） 即

36、：A(2)A(5) A(3) A(4) A(7) A(1) A(8) A(6),2路归并的非递归实现 (1)可以很容易地消除递归，因为递归只是简单地重复分割元素序列，直到序列的长度变成1为止。当序列的长度变为1时进行归并操作。长度为1的序列归并为长度为2的序列；长度为2的序列归并为长度为4的序列 ；具体实现可有多种方法。可附设一队列，将一遍所得各有序子序列的起止界限存入队列，然后从队列中每次删除两个元素，得到两个有序子序列的端点，将这两个子序列归并后得到的一个新的子序列的起止界限存入队列，如此重复直至队列中只有一个界限为止。,（2）自然归并是基本归并分类的一种变形。基本思想是先扫描一趟数据，得

37、到有序子序列，然后对这些子序列进行归并。例如，元素序列4,8,3,7,1,5,6,2 中含有有序子序列4,8,3,7,1,5,6,2。一个极端的例子是，当原始数据有序时，自然归并将准确地识别该序列而不必进行归并，因此自然归并在最好情况下的时间复杂度为O(n)。,（3） 复制开销的降低可以通过轮流地将A归并到B，再将B归并到A的策略而减少数据复制的次数。,6. 以比较为基础分类的时间下界,任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为：(nlogn)利用二元比较树证明。假设参加分类的n个关键字A(1),A(2),A(n)互异。任意两个关键字的比较必导致A(i)A(j)的结果。以二元

38、比较树描述元素间的比较过程：若A(i)A(j)，进入下一级的右分支,算法在外部结点终止。 从根到某外结点的路径代表某个特定输入情况下一种唯一的分类排序序列。路径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。故，以比较为基础的分类算法的最坏情况下界等于该算法对应的比较树的最小高度。, 由于n个关键字有n!种可能的排列，所以二元比较树中将有n!个外部结点：每种排列对应于某种特定输入情况下的分类情况，每个外部结点表示一种可能的分类序列。 设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个

39、外结点。记算法在最坏情况下所作的比较次数为T(n)，则有T(n)=k：生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1；根据和的分析，有： n!2T(n),化简：当n1时，有n!n(n-1)(n-2)(n/2 )(n/2)n/2当n4时，有 T(n)(n/2)log(n/2)(n/4)logn故，任何以比较为基础的分类算法的最坏情况的时间下界为： (nlogn),3.5 快速分类,1. 问题描述分类问题 2. 划分快速分类是一种基于划分的分类方法；,选取待分类集合A中的某个元素t，按照与t的大小关系重 新整理A中元素，使得整理后的序列中所有在t以前出现的元素均小于等于t，而所

40、有出现在t以后的元素均大于等于t。这一元素的整理过程称为划分（Partitioning）。元素t称为划分元素。,划分,通过反复地对待分类集合进行划分达到分类目的的分类算法。,快速 分类,划分过程（PARTITION）的算法描述,算法3.12 用A(m)划分集合A(m:p-1)procedure PARTITION(m,p)integer m,p,i; global A(m:p-1)vA(m);im /A(m)是划分元素/looploop ii+1 until A(i)v repeat / i由左向右移/loop pp-1 until A(p)v repeat /p由右向左移/if ip the

41、ncall INTERCHANGE(A(i),A(p)/交换else exit /退出endifrepeatA(m)A(p)； A(p)v /划分元素在位置p/ end PARTITION,注：算法对集合A(m:p-1)进行划分。并使用待划分区间的第一个元素A(m)作为划分元素A(p)不在划分区间内，但被定义，且A(p）A(m)，用于限界,两点改进（参见严蔚敏的教材） （1）可以不交换元素； （2）无需假设A(p)。,例4.5 划分实例(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i pA: 65 70 75 80 85 60 55 50 45 + 2 9|

42、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 +,划分元素定位于此,交换划分元素,(1) (2) (3) (4) (5) (6) (7) (8) (9) A: 45 70 75 80 85 60 55 50 45A: 45 70 75 80 85 60 55 50 70A: 45 50 75 80

43、 85 60 55 50 70A: 45 50 75 80 85 60 55 75 70A: 45 50 55 80 85 60 55 75 70A: 45 50 55 60 85 85 80 75 70,划分元素定位于此,交替移动元素,例4.5 划分实例（不交换元素）,Pivot=65,65,65 70 75 80 85 60 55 50 45,经过一次“划分”后，实现了对集合元素的调整：其中一个子集合的所有元素均小于等于另外一个子集合的所有元素。按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类。,3.

44、快速分类 通过反复使用划分过程PARTITION实现对集合元素分类的算法。 算法3.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+1call PARTITION(p,j) /出口时，j待出此次划分后划分元素所在的坐标位置/call QUICKSORT(p,j-1) /前一子集合上递归调用call QUICKSORT(j+1,q

45、) /后一子集合上递归调用endifend QUICKSORT 时间复杂度： Q(n)=P(n)+Q(m)+Q(n-m),4. 快速分类分析 统计的对象：元素的比较次数，记为：C(n) 两点假设参加分类的n个元素各不相同PARTITION中的划分元素v是随机选取的（针对平均情况的分析） 随机选取划分元素：在划分区间m,p随机生成某一坐标：iRANDOM(m.p-1)；调换A(m)与A(i):vA(i);A(i) A(m);im 作用：将随机指定的划分元素的值依旧调换到A(m)位置。 之后，算法主体不变，仍从A(m)开始执行划分操作。,递归层次,QuickSort(1,n),QuickSort(

46、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处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少少1： 理想情况，第一级少1，第二级少2，第三级少4

47、， ；（两个子列规模相当） 最坏情况，每次仅减少1（如集合元素已经按照递增或递减顺序排列）（两子列规模悬殊）,最坏情况分析记最坏情况下的元素比较次数是Cw(n)；PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素个数r。最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。即：Cw(n)= = (n2),平均情况分析平均情况是指集合中的元素以任意一种顺序排列，且任选所有可能的元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。设调用PARTITION(m,p)时，所选取划分元素v恰好是A(m:p-1)中的第j小元素（1jp-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m), mjp。则有，其中，n+1是PARTITION第一次调用时所需的元素比较次数。CA(0) = CA(1) = 0,