算法第四章

4.1一般方法4.2二分检索4.3找最大和最小元素4.4归并分类4.5快速分类4.6选择问题4.7斯特拉森矩阵乘法第四章分治法4.1一般方法分治法的思想:将一个输入规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。问题(N个输入)子问题1子问题2子问题K…子问题1子问题2子问题k…相同类型合并解分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。步骤：分（devide）二分为主多分比二分更好吗？治（conquar）递归调用，当规模足够小时直接处理组（combine）分治法问题特征：1)问题规模小到一定的程度就非常容易解决所有问题的共性特征2)问题可分解为若干个规模较小的同类问题递归策略[分]3)子问题的解可以合并为该问题的解若不具备，可用贪心或动态规划4)子问题是相互独立的保证采用分治法效率高，否则更适合采用动态规划分治策略DANDC的抽象化控制procedureDANDC(p,q)globaln,A(1:n);integerm,p,q;//1≤p≤q≤n//ifSMALL(p,q)thenreturn(G(p,q))elsemDIVIDE(p,q)return(COMBINE(DANDC(p,m),DANDC(m+1,q)))endifendDANDC判断输入规模q-p+1是否足够小,可直接求解G是求解该规模问题的函数分割函数,p≤m≤q,原问题被分为A(p:m)和A(m+1:q)两个子问题合并函数,将两个子问题的解合并为原问题的解原问题为A(1:n),最初调用函数应该是DANCE(1,n);DANDC(p,q)是计算A(p:q)子问题的解4.1一般方法2分策略DANDC的计算时间倘若所分成的两个子问题的输入规模大致相等,则分治策略DANDC的计算时间可表示为：说明：T(n)是输入规模为n的分治策略的计算时间g(n)是对足够小的输入规模能直接计算出答案的时间f(n)是COMBINE函数合成原问题解的计算时间g(n)n足够小2T(n/2)+f(n)否则T(n)=4.1一般方法k分法的复杂性分析一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阈值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：11)()/()1()(nnnfmnkTOnT通过迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤nmi+1时，T(mi)≤T(n)T(mi+1)。二分检索问题描述:已知一个按非降序排列的元素表a1,a2,…,an,判定某个给定元素x是否在该表中出现，若是,则找出该元素在表中的位置,并置于j,否则置j为0二分检索原理将二分检索问题问题表示为：I=(n,a1,…,an,x)选取一个下标k，可得到三个子问题：I1=(k-1,a1,…,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,…,an,x)对所求解的问题（或子问题）所选的下标都是中间元素的下标，k=(n+1)/2」4.2二分检索procedureBINSRCH(A,n,x,j)intlow,high,mid,j,n;low1;highn;while（low=high）domid(low+high)/2;/*取中间值*/casexA[mid]:highmid-1/*寻找前一半*/xA[mid]:lowmid+1/*寻找后一半*/else:jmid;return;/*检索成功,结束*/endcaserepeatj0;/*检索失败*/endBINSRCH二分检索算法检索x=9,9=A[5],一次比较就成功,最好情况-15-6079235482101A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]①②③③④②③④检索x=-15,-15A[5],-15A[2],-15=A[1],3次比较,成功检索x=101,101A[5],101A[7],101A[8],101=A[9],4次比较,成功检索x=8,8A[5],8A[2],8A[3],8A[4],4次比较,不成功检索二分检索实例:设在A(1:9)中顺序放了以下9个元素：用五个特性判断是否是一个算法根据算法的描述，满足五个特性，是算法证明算法是否正确如果n=0，则不进入循环，j=0，算法终止否则就会进入循环与数组A中的元素进行比较如果x=A[mid]，则j=mid，检索成功，算法终止否则，若xA(mid)，则缩小到A(low)和A(mid-1)之间检索若xA(mid)，则缩小到A(mid+1)和A(n)之间检索按上述方式缩小检索区总可以在有限步内使lowhigh如果出现这种情况，说明x不在A中，j=0，算法终止二分检索算法正确性证明：二分检索算法所需的空间和时间所需空间:用n个位置存放数组A，还有low,high,mid,x,j五个变量需要存储，共需空间n+5所需计算时间:对于计算时间，需要分别考虑以下几种情况：成功检索的最好情况、平均情况、最坏情况不成功检索的最好情况、平均情况、最坏情况4.2二分检索-15-6079235482101A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]3234132343334433344成功检索有n种情况，不成功检索有n+1种情况成功：不成功：不论检索是否成功，算法的执行过程都是x与一系列中间元素A[mid]的比较过程，我们可以用一棵二元比较树来描述算法的执行过程二元比较树内结点表示一次元素的比较,存放一个mid值外结点表示不成功检索的一种情况592-61-1530754476238829101一条路径表示一个元素的比较序列4.2二分检索二分检索的时间复杂度定理4.2:若n在区域[2k-1,2k)中，则对于一次成功的检索，二分检索算法至多作k次比较，而对于一次不成功的检索，或者作k-1次比较或者作k次比较。对前面二分检索实例n=9,n∈[23,24),已分析过成功检索和不成功检索的各种情况下的比较次数≤4,易知:Θ(logn)Θ(logn)Θ(logn)Θ(logn)Θ(logn)Θ(1)不成功的检索成功的检索最坏情况平均情况最好情况计算时间4.2二分检索Notes:E=I+2n的证明1.在n=1时显然成立2.设内节点为n-1时成立，3.内节点为n时把最远的内节点（i级）拿掉，替换为一个外节点E’=E–2i+(i-1)=E–i-1I’=I–(i-1)E’=I’+2n-2=E=E’+i+1=I’+2n-1+i=I–(i-1)+2n-1+i=I+2n成功检索平均比较数S(n)=I/n+1不成功检索平均比较数U(n)=E/(n+1)推导得：S(n)=(1+1/n)U(n)-1S(n)=Θ(logn)关于确切比较次数的讨论：•BINSRCH的一次比较假设不合理，是为了降低分析复杂度的权宜之计，但对近似表示无影响•实际上应该用（*）替代BINSRCH相应语句•每次循环固定一次比较的BINSRCH1算法的提出对于成功检索：最好最坏平均BINSRCH1log(n)log(n)BINSRCH(*)22log(n)1.5log(n)BINSRCH1log(n)+1log(n)+1log(n)+1以比较为基础检索的时间下界思考:对于已排序的n个元素,检索某元素x是否出现,是否存在以比较为基础的检索算法,在最坏情况下该算法的计算时间比二分检索算法的计算时间更低对于以比较为基础的检索算法的分析，采取构建二元比较树的方式。二元比较树-顺序检索有n个如下关系的元素:A(1)A(2)…A(n),检索一给定元素X是否在A中出现X:A(1)X:A(2)X:A(n)不成功不成功不成功不成功线性检索二元比较树-二分检索X:A([(n+1)/2])X:A([(3n+1)/4])X:A([(n+1)/4])X:A(n)])X:A([(2n+1)/2]+1)X:A([(2n+1)/2]-1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功…………以比较为基础检索的时间下界定理4.3:设A(1:n)含有n(n≥1)各不同的元素，排序为A(1)A(2)…A(n)。又设以比较为基础去判断是否x∈A(1:n)的任何算法在最坏情况下所需的最小比较次数是FIND(n)，那么FIND(n)≥log(n+1)证明：任何以元素比较为基础的检索算法，都能描述成二元比较树不论成功、不成功检索，对树而言最坏情况都是根到最远叶节点距离k(内节点最大级数，树高)，对于算法而言FIND(n)只能不小于这个值为了保证成功检索正常，树至少有n个内节点n≤2k-1,FIND(n)≥k≥log(n+1)以比较为基础检索的时间下界定理表明:任何一种以比较为基础的算法，其最坏情况下的计算时间都不可能低于O(logn)，也就是不可能存在其最坏情况下计算时间比二分检索算法的计算时间数量级还低的算法。思考：•三分（多分）检索会得到更优的结果吗？不会，画二分展开树（二元比较是基本能行操作）会发现树高增加4.3找最大和最小元素问题描述：在含有n个不同元素的集合中同时找出它的最大和最小元素procedureSTRAITMAXMIN(A,n,max,min)inti,n;max←min←A[1];fori←2tondo{ifA[i]maxthenmax←A[i];ifA[i]minthenmin←A[i];}endSTRAITMAXMIN直接算法:依次比较n-1个元素,同时记录下最大、最小的元素ifA[i]maxthenmax=A[i];elseifA[i]minthenmin=A[i];直接算法的时间复杂度在最好、最坏、平均情况下均为2(n-1)改进后的计算时间:(元素升序)最好情况为(n-1)(元素降序)最坏情况为2(n-1)平均情况为3/2(n-1)采用分治策略求最大最小元素I=(n,A(1),…,A(n))划分为I1=(n/2,A(1),…,A(n/2))I2=(n-n/2,A(n/2+1),…,A(n))结果的合并分治法求最大和最小元素procedureMAXMIN(i,j,fmax,fmin)inti,j;globaln,A(1:n);casei=j:fmax←fmin←A[i]i=j-1:ifA[i]A[j]then{fmax←A[j];fmin←A[i];}else{fmax←A[i];fmin←A[j];}else:{mid(i+j)/2;callMAXMIN(i,mid,gmax,gmin)callMAXMIN(mid+1,j,hmax,hmin)fmax←max(gmax,hmax);fmin←min(gmin,hmin);}endcaseendMAXMIN只有一个或两个元素时递归调用部分两个子问题的答案进行合并4.3找最大和最小元素A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素2213-5-815601731471,9,1,3,4,5,3,3,1,2,1,5,6,9,8,9,6,7,①22,13②-5,-5③22,-5④15,-8⑤22,-8⑨60,-8⑧60,17⑥60,17⑦47,31实例:A(1:n),n=9,元素具体如下表所示:4.3找最大和最小元素过程MAXMIN的时间复杂度MAXMIN的元素比较次数当n=2k(k是某个正整数)时，有T(n)