计算机算法基础(第二章).ppt

2019/11/24,计算机算法基础,2019/11/24,第二章分治法“分”而治之,2.1一般方法对大规模问题的求解利用分治法求解大规模问题,1.基本思想在问题的输入规模很大时，无法直接求解，则采用将整个问题分成若干个小问题后分而治之。,一般情况下，子问题与原始问题“同质”,2019/11/24,算法2.1分治策略的抽象化控制procedureDANDC(p,q)globaln.A(1:n);integerm,p,q;/1pqn/ifSMALL(p,q)thenreturn(G(p,q)elsemDIVIDE(p,q)/pmq/return(COMBINE(DANDC(p,m),DANDC(m+1,q)endifendDANDC,注：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.分治策略的抽象化控制,2019/11/24,DANDC的计算时间若所分成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下：g(n)n足够小T(n)=2T(n/2)+f(n)否则注：T(n)：表示输入规模为n的DANDC计算时间g(n)：表示对足够小的输入规模直接求解的计算时间f(n)：表示COMBINE对两个子区间的子结果进行合并的时间（该公式针对具体问题有各种不同的变形）,2019/11/24,2.2二分检索（折半查找）,1.问题的描述已知一个按非降次序排列的元素表a1,a2,an,判定某给定的元素x是否在该表中出现。若是，则找出x在表中的位置并返回其所在下标若非，则返回0值。,2019/11/24,分治求解策略分析：定义问题的形式描述：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上的求解可再次采用分治方法划分后求解（递归过程）,2019/11/24,2.二分检索算法,算法2.3二分检索procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low1;highn;whilelowhighdomidcasexA(mid):lowmid+1else:jmid;returnendcaserepeatendNIBSRCH,注：给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。若是，置j，使得x=A(j)若非，j=0,2019/11/24,例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中检索x=101，-14，82。执行轨迹见下表1,成功的检索,不成功的检索,成功的检索,2019/11/24,3.算法的正确性证明定理2.1过程BINSRCH(A,n,x,j)能正确运行证明：1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都能按要求正确运行即首先满足确定性和能行性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，算法终止。,2019/11/24,4.性能分析,1）空间特性n+5个空间位置(n)2)时间特性区分以下情况，并进行相应的分析成功检索：所检索的x出现在A中。成功检索情况共有n种：x恰好是A中的某个元素，A中共有n个元素，故有n种可能的情况不成功检索：所检索的x不出现在A中。不成功检索情况共有n+1种：xA(n)成功/不成功检索的最好情况：执行步数最少，计算时间最短成功/不成功检索的最坏情况：执行步数最多，计算时间最长成功/不成功检索的平均情况：一般情况下的计算时间,2019/11/24,实例分析（例2.1）,频率计数特征while循环体外语句的频率计数为1集中考虑while循环中的x与A中元素的比较（其它运算的频率计数与之有相同的数量级）假定只需一次比较就可确定case语句控制是三种情况的哪一种。查找每个元素所需的元素比较次数统计如下：,A元素-15-6079235482101成功检索比较次数323413234不成功检索比较次数3334433344,2019/11/24,成功检索最好：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次,2019/11/24,二元比较树,算法执行过程的主体是x与一系列中间元素A(mid)比较。可用一棵二元树描述这一过程，并称之为二元比较树。构造：比较树由称为内结点和外结点的两种结点组成：内结点：表示一次元素比较，用圆形结点表示，存放一个mid值；代表一次成功检索；外结点：在二分检索算法中表示一种不成功检索的情况，用方形结点表示。路径：表示一个元素的比较序列。,例2.1的二元比较树,2019/11/24,基于二元比较树的分析若x在A中出现，则算法的执行过程在一个圆形的内结点处结束。若x不在A中出现，则算法的执行过程在一个方形的外结点处结束外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。,例2.1的二元比较树,2019/11/24,定理2.2若n在区域2k-1,2k)中，则对于一次成功的检索，BINSRCH至多做k次比较；对于一次不成功的检索，或者做k-1次比较，或者做k次比较。证明：要点：成功检索都在内结点处结束，不成功检索都在外结点处结束当2k-1n2k时，所有内结点在1至k级，所有外结点在第k-1级或第k级，故：成功检索在i级终止所需要的元素比较次数是i不成功检索在i级外部结点终止的元素比较次数是i-1,2019/11/24,BINSRCH计算复杂度的理论分析,1）不成功检索的最好、最坏和平均情况的计算时间均为外结点处在最末的两级上；2）最好情况下的成功检索的计算时间为最坏情况下的成功检索的计算时间为,2019/11/24,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)=,2019/11/24,4.以比较为基础检索的时间下界,问题：设n个元素的数组A(1:n)有A(1)A(2)A(n)。检索一给定元素x是否在A中出现。定理2.2给出了二分检索算法的时间下界，是否预计还存在有以元素比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有更低的数量级?以比较为基础的算法：假定算法中只允许进行元素间的比较，而不允许对它们实施其它运算。,2019/11/24,注：每个内结点表示一次元素的比较。每棵比较树中恰好含有n个内结点，分别与n个不同i值相对应；每个外结点对应一次不成功的检索，并恰好又n+1个外结点对应于n+1中不成功检索的情况。,任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。,2019/11/24,以比较为基础的有序检索问题最坏情况的时间下界定理2.3设A(1:n)含有n(n1)个不同的元素，排序为A(1)A(2)maxthenmaxA(i)endififA(i)maxthenmaxA(i)endifelseifA(i)2化简得，C(n)=2C(n/2)+3=5n/2-3按照同样的假设，重新估算STRAITMAXMIN算法的比较次数为：3(n-1)。考虑MAXMIN算法递归调用的开销，此时MAXMIN算法的效率可能还不如STRAITMAXMI算法。,2019/11/24,结论：如果A中的元素间的比较代价远比整型数（下标）的比较昂贵，则分治方法将产生一个效率较高的算法；反之，可能仅得到一个低效的算法。故，分治策略只能看成一个较好的但并不总是成功的算法设计指导。,2019/11/24,2.4归并分类,1.分类问题排序给定一n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。分类：内排序，外排序常见内排序方法：冒泡排序插入排序归并排序快速排序堆排序,2019/11/24,2.插入分类算法2.7插入分类procedureINSERTIONSORT(A,n)/将A(1：n)中的元素按非降次序分类，n1/A(0)-/设置初始边界值forj2tondo/A(1:j-1)已分类/itemA(j);ij-1whileitemA(i)do/0i1,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),2019/11/24,归并分类示例,设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,2019/11/24,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|423，861，254，450，520）第四次归并：（179，285，310，351，652|423，861，254，450，520）进入右分枝的划分与归并过程（略）,2019/11/24,3）用树结构描述归并分类过程,2019/11/24,4.归并分类算法的改进,1）算法2.8存在的问题递归层次太深在MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。在集合含有仅相当少的元素时，较深层次的递归调用使得时间过多地消耗在处理递归上。元素在数组A和辅助数组B之间的频繁移动每次归并，都要首先将A中的元素移到B中，在由B复制到A的对应位置上。,2019/11/24,2）改进措施针对递归层次问题采用能在小规模集合上有效工作的其它算法，直接对小规模集合处理。如INSERTIONSORT算法针对元素频繁移动问题采用一个称为链接信息数组LINK（1：n）的数据结构，记录归并过程中A中的元素相对于其排序后在分类表中位置坐标的链接关系。LINK(i)取值于1，n，是指向A的元素的指针：在分类表中它指向下一个元素在A中的位置坐标。,2019/11/24,例：LINK(1)(2)(3)(4)(5)(6)(7)(8)64713080该表中含有两个子表，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中的链接关系取得。,2019/11/24,改进后的归并分类模型,算法2.10使用链接信息数组的归并分类模型procedureMERGESORT1(low,high,p)/利用链接信息数组LINK(1:n)将全程数组A(low:high)按非降次序分类。LINK中值表示按分类次序给出A下标的表，并把p置于该表的开始处/globalA(low:high),LINK(low,high)ifhigh-low+116/当集合中的元素个数足够少(1时，有n!n(n-1)(n-2)()(n/2)n/2当n4时，有T(n)(n/2)log(n/2)(n/4)logn故，任何以比较为基础的分类算法的最坏情况的时间下界为：(nlogn),2019/11/24,2.5快速分类,1.问题描述分类问题2.划分快速分类是一种基于划分的分类方法；划分：选取待分类集合A中的某个元素t，按照与t的大小关系重新整理A中元素，使得整理后的序列中所有在t以前出现的元素均小于等于t，而所有出现在t以后的元素均大于等于t。这一元素的整理过程称为划分（Partitioning）。元素t称为划分元素。快速分类：通过反复地对待排序集合进行划分达到分类目的的分类算法。,2019/11/24,划分过程（PARTITION）的算法描述,算法2.2用A(m)划分集合A(m:p-1)procedurePARTITION(m,p)integerm,p,i;globalA(m:p-1)vA(m);im/A(m)是划分元素/looploopii+1untilA(i)vrepeat/i由左向右移/looppp-1untilA(p)vrepeat/p由右向左移/ifipthencallINTERCHANGE(A(i),A(p)elseexitendifrepeatA(m)A(p)；A(p)v/划分元素在位置p/endPARTITION,2019/11/24,注：算法对集合A(m:p-1)进行划分。并使用待划分区间的第一个元素A(m)作为划分元素A(p)不在划分区间内，但被定义，且A(p）A(m)，用于限界,2019/11/24,例2.5划分实例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ipA:657075808560555045+29|A:654575808560555070+38|A:654550808560557570+47|A:654550558560807570+56|A:654550556085807570+65|A:604550556585807570+,划分元素定位于此,交换划分元素,2019/11/24,经过一次“划分”后，实现了对集合元素的调整：其中一个子集合的所有元素均小于等于另外一个子集合的所有元素。按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类。,2019/11/24,3.快速分类通过反复使用划分过程PARTITION实现对集合元素分类的算法。算法2.13快速分类procedureQUICKSORT(p,q)/将数组A(1:n)中的元素A(p),A(q)按递增的方式分类。A(n+1)有定义，且假定A(n+1)+/integerp,q;globaln,A(1:n)ifpqthenjq+1/进入时，A(j)定义了划分区间p,q的上界，初次调用时j=n+1callPARTITION(p,j)/出口时，j待出此次划分后划分元素所在的坐标位置/callQUICKSORT(p,j-1)/前一子集合上递归调用callQUICKSORT(j+1,q)/后一子集合上递归调用endifendQUICKSORT,2019/11/24,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)开始执行划分操作。,2019/11/24,递归层次,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处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1：理想情况，第一级少1，第二级少2，第三级少4，；最坏情况，每次仅减少1（如集合元素已经按照递增或递减顺序排列）,2019/11/24,最坏情况分析记最坏情况下的元素比较次数是Cw(n)；PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。即：Cw(n)=(n2),2019/11/24,平均情况分析平均情况是指集合中的元素以任一一种顺序排列，且任选所有可能的元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。设调用PARTITION(m,p)时，所选取