第2章递归与分治策略 (2)PPT讲稿.ppt

《第2章递归与分治策略 (2)PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第2章递归与分治策略 (2)PPT讲稿.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章递归与分治策略(2)第1页，共39页，编辑于2022年，星期一2算法设计与分析算法设计与分析 递归与分治递归与分治可分解性：复杂性随问题规模的减少而减少；可分解性：复杂性随问题规模的减少而减少；递归性：子问题具有相同的模式，因而可以用递归递归性：子问题具有相同的模式，因而可以用递归方法处理；方法处理；可归并性：子问题的解不是原问题的解时必须能可归并性：子问题的解不是原问题的解时必须能把子问题的解归并成原问题的解把子问题的解归并成原问题的解;独立性：子问题相互独立，没有交叉、重复。独立性：子问题相互独立，没有交叉、重复。分治策略的适用条件分治策略的适用条件第2页，共39页，编辑于2022年

2、，星期一3算法设计与分析算法设计与分析 递归与分治递归与分治如何分解？大量实践中发现，在用分治法设计算法时，最好使大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同子问题的规模大致相同。这种使子问题规模大致相等。这种使子问题规模大致相等的做法是出自的做法是出自一种一种平衡平衡(balancing)(balancing)子问题子问题的思想，它的思想，它几乎总是比子问题规模不等的做法要好。几乎总是比子问题规模不等的做法要好。子问题规模大致相同、平衡，这样最有效。通常子问题规模大致相同、平衡，这样最有效。通常 k=2.第3页，共39页，编辑于2022年，星期一4算法设计与分析算法设计与

3、分析 递归与分治递归与分治 Divide-and-Conquer(P)if(|P|=n0)Adhoc(P);直接求解问题p divide P into smaller subinstances P1,P2,.,Pk;for(i=1;i 递归与分治递归与分治设问题P(n)分解成k个规模为n/m的子问题,阀值n0=1,求解P(1)的时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则分治法解规模为n的问题的最坏时间复杂性函数T(n)满足:T(n)=算法的时间复杂性 Divide-and-Conquer(P)if(|P|=n0)Adhoc(P);divide P into sm

4、aller subinstances P1,P2,.,Pk;for(i=1;i=k;i+)yi=Divide-and-Conquer(Pi);return Merge(yl,.,yk);f(n)kT(n/m)T(1)=O(1)T(n)=kT(n/m)+f(n)解得:适用问题大数相乘,矩阵乘法,快速富立叶变换,棋盘覆盖,排序,选择 等.O(1)第5页，共39页，编辑于2022年，星期一 已知不重复且从小到大排列的已知不重复且从小到大排列的m个整数的数组个整数的数组A1.m,m=2K,K为正整数为正整数.对于给定的整数对于给定的整数c,要求找到一个下标要求找到一个下标i,使得使得Ai=c.找不到返

5、回找不到返回0.function search(c)i:=1;1 while Aic and i 递归与分治递归与分治 二分二分查找查找第6页，共39页，编辑于2022年，星期一 算法1-2:二分查找例例题题1-1最坏情况Tmax(m)=O(logm)function b-search(c)L:=1;U:=m;found:=false;while not found and U=L do i:=(L+U)div2;if c=Ai then found:=trueelse if cAi then L:=i+1 else U:=i-1 if found then b-search:=1 else

6、b-search:=0 7算法设计与分析算法设计与分析 递归与分治递归与分治 二分二分查找查找第7页，共39页，编辑于2022年，星期一8从无序的数组a0:n-1中寻找最大与最小元素方法一：找最大元素：n-1次比较 找最小元素：n-2次比较总计：2n-3次比较方法二（分治法）左右两部分分别求max1，min1和max2，min2 合成：fmax=max(max1，max2)fmin=min(min1，min2)寻找最大与最小元素寻找最大与最小元素算法设计与分析算法设计与分析 递归与分治递归与分治 寻找最大与最小元素寻找最大与最小元素第8页，共39页，编辑于2022年，星期一9递归方程 0 n=

7、1T(n)=1 n=2 T(n/2)+T(n/2)+2 n2T(n)=3n/2 2 比较次数优于方法一。算法设计与分析算法设计与分析 递归与分治递归与分治 寻找最大与最小元素寻找最大与最小元素第9页，共39页，编辑于2022年，星期一10算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法通常，在分析算法的复杂性时，加法和乘法当作基本运算，即执行通常，在分析算法的复杂性时，加法和乘法当作基本运算，即执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。处理速度的常数。这个假定仅在硬件能对整

8、数直接表示和处理时才合理。然而，这个假定仅在硬件能对整数直接表示和处理时才合理。然而，在处理很大整数时，硬件无法直接表示和处理。而用浮点数来表在处理很大整数时，硬件无法直接表示和处理。而用浮点数来表示则只能近似值，计算结果中的有效数字也受到限制。若要精确示则只能近似值，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，地表示大整数并在计算结果中要求精确地得到所有位数上的数字，必须用软件方法来实现大整数的算术运算。必须用软件方法来实现大整数的算术运算。2.4 大整数的乘法算法算法问题问题:设设X,Y是两个是两个n位二进制数位二进制数,求求XY.第1

9、0页，共39页，编辑于2022年，星期一11如何设计两个大整数的乘法运算的有效的算法？如何设计两个大整数的乘法运算的有效的算法？要求：大整数超出要求：大整数超出longint表示范围，而浮点表示不精确。表示范围，而浮点表示不精确。假设：乘法时间远大于加减法、移位运算假设：乘法时间远大于加减法、移位运算将两个一位数的乘法或加法看作一步运算，那么，两个将两个一位数的乘法或加法看作一步运算，那么，两个N位数位数X*Y相乘，需要相乘，需要O(N2)时间时间算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法分治算法思路分治算法思路:若两个若两个1位数相乘或相加看作位数相乘或相加

10、看作1步运算步运算,按传统乘法按传统乘法需需O(n2)次运算次运算.将每个将每个n(n=2K)位的二进制整数分为位的二进制整数分为2段段,每段的长每段的长为为n/2位位X=A2n/2+BY=C2n/2+D。第11页，共39页，编辑于2022年，星期一T(1)=O(1)T(n)=3T(n/2)+O(n)12算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法计算计算XY须须3次次n/2位整数的乘法位整数的乘法,6次加次加.减和减和2次移位次移位XY(A2n/2+B)(C2n/2+D)AC2n+(AD+CB)2n/2+BD T(n)=T(1)=O(1)T(n)=4T(n/2

11、)+O(n)计算计算XY须须4次次n/2位整数的乘法位整数的乘法,3次不超过次不超过2n位的整数加法位的整数加法,2次次移位移位(乘乘2n和乘和乘2n/2).XY的的T(n)满足满足解得解得T(n)=O(n2)T(n)=解得 T(n)=O(nlog3)没有改善改进:XYAC2n+(A-B)(D-C)+AC+BD2n/2+BD算法算法如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。第12页，共39页，编辑于2022年，星期一

12、13算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法 S=SIGN(X)*SIGN(Y)；X:=ABS(X)；Y:=ABS(Y)；if n=l then if(X=1)and(Y=1)then return(S)else return(0)else A:=X的左边n/2位；B:=X的右边n/2位；C:=Y的左边n/2位；D:=Y的右边n/2位；m1:=MULT(A，C，n/2)；m2:=MULT(A-B,D-C，n/2)；m3:=MULT(B，D，n/2)；S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)；return(S)X,Y为2个小于2n的二进制

13、整数，返回结果为X和Y的乘积XYfunction MULT(X,Y,n)大数相乘的分治递归算法大数相乘的分治递归算法二进制大整数乘法同样可应用于十进制大整数的乘法存放XY的符号存放三个乘积算法算法第13页，共39页，编辑于2022年，星期一142.5 2.5 矩阵相乘的矩阵相乘的StrassenStrassen法法算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法求出矩阵求出矩阵C的的n2个元素所需的时间为个元素所需的时间为0(n3)。常规算法常规算法:设矩阵设矩阵A=(aij)n n,B=(bij)n n,C=A B=(cij)n n

14、计算计算C共需共需n n2个乘法个乘法,n2(n-1)个加法个加法.T(n)=O(n3)分治法分治法1969年，年，Strassen采用了类似于在大整数乘法中用过的分治技术，采用了类似于在大整数乘法中用过的分治技术，将计算将计算2个个n阶矩阵乘积所需的计算时间改进到阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2.81)。第14页，共39页，编辑于2022年，星期一T(2)=O(1)T(n)=8T(n/2)+O(n2)15分治算法分治算法:划分划分A,B为四个为四个n/2(n=2K)阶方阵阶方阵,则则:C11=A11B11+A12B21C12=A11B11+A12B21C21=A11B

15、11+A12B21C22=A11B11+A12B21若若n=2,可直接计算可直接计算C;若若n2,C需需8个个n/2阶方阵的乘法和阶方阵的乘法和4个加法个加法.T(n)=得得:T(n)=O(n3)算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法第15页，共39页，编辑于2022年，星期一16改进C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7M1=A11(B12-B21)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B

16、11+B22)M6=(A12+A22)(B21+B22)M7=(A11-A21)(B11+B12)验证:C22=M5+M1-M3-M7 =(A11+A22)(B11+B22)+A11(B12-B21)-(A21+A22)B11-(A11-A21)(B11+B12)=A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22-A21B11-A22B11-A11B11 -A11B12+A21B11+A21B12 =A21B12+A22B22算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法第16页，共39页，编辑于

17、2022年，星期一procedure STRASSEN(n,A,B,C)；if n=2 then MATRIX_MULTIPLY(A,B,C)else 将矩阵A和B分块；STRASSEN(n/2，A11，B12-B22，M1)；STRASSEN(h/2，A11+A12，B22，M2)；STRASSEN(n/2，A21+A22，B11，M3)；STRASSEN(n/2，A22，B21-B11，M4)；STRASSEN(n/2，A11+A22，B11+B22，M5)STRASSEN(n/2，A12-A22，B21+B22，M6)；STRASSEN(n/2，A11+A21，B11+B12，M7)C:

18、=矩阵相乘Strassen算法算法算法17算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法第17页，共39页，编辑于2022年，星期一18算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法复杂度改进为：T(n)=O(Nlog7)O(N2.81)理论意义：突破了O(N3)界限实际应用问题：递归；占用空间多；对于非2k 阶方阵的处理最好的成果：O(N2.37)继续按2*2分解。能否达到O(N2)？Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。

19、因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。T(n)=T(2)=O(1)T(n)=7T(n/2)+18(n/2)2 得:T(n)=O(nlog7)=O(n2.81)分析:第18页，共39页，编辑于2022年，星期一(a)(b)(c)(d)问题陈述问题陈述:在一个在一个2k 2k个方格组成的棋盘中个方格组成的棋盘中,恰有一方格残缺恰有一方格残缺,残缺方格的位置有残缺方格的位置有22k种。故对任何种。故对任何k0,残缺棋盘有残缺棋盘有22k种种.要求用要求用L型骨牌覆盖残缺棋盘上的所有方格且任何型骨牌覆盖残缺棋盘上的所有方

20、格且任何2个个L型骨牌型骨牌不得重叠覆盖不得重叠覆盖。192k 2k的棋盘覆盖中，用到的棋盘覆盖中，用到的骨牌数为的骨牌数为(4k-1)/32.6 2.6 棋盘覆盖棋盘覆盖算法设计与分析算法设计与分析 递归与分治递归与分治 棋盘覆盖(a)(b)(c)(d)11 122 233 34 4455 5第19页，共39页，编辑于2022年，星期一20分治算法:当k0时,将2k 2k棋盘分割为4个2k-1 2k-1子棋盘 残缺方格必位于4个子棋盘之一其余3个子棋盘中无残缺方格为此将剩余3棋盘转化为残缺棋盘.用一个L型骨牌覆盖这3个较小棋盘的结合处.这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方

21、格，原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1 1棋盘.算法设计与分析算法设计与分析 递归与分治递归与分治 棋盘覆盖第20页，共39页，编辑于2022年，星期一21算法分析:设T(k)为覆盖2k 2k残缺棋盘的时间,当k=0时覆盖它需要常数时间O(1)当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k-1),T(k)=O(1)4T(k-1)+O(1)得:T(k)=(4k)与所需骨牌数同阶算法设计与分析算法设计与分析 递归与分治递归与分治 棋盘覆盖第21页，共39页，编辑于2022年，星期一void

22、 ChessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return；int t=tile+，/L型骨牌号 s=size2；/分割棋盘 /覆盖左上角子棋盘覆盖左上角子棋盘 if(dr tr+s&dc 递归与分治递归与分治 棋盘覆盖第22页，共39页，编辑于2022年，星期一/覆盖右上角子棋盘覆盖右上角子棋盘 if(dr=tc+S)/特殊方格在此棋盘中 ChessBoard(tr，tc+s，dr，dc，S)；else/此棋盘中无特殊方格 /用t号骨牌覆盖左下角 Boardtr+s-1tc+s=t；/覆盖其余方格 Chessboard(

23、tr，tc+s，tr+s-1，tc+s，s)；./覆盖左下角子棋盘覆盖左下角子棋盘 if(dr=tr+s&dc 递归与分治递归与分治第23页，共39页，编辑于2022年，星期一/覆盖右下角子棋盘覆盖右下角子棋盘 if(dr=tr+s&dc=tc+S)/特殊方格在此棋盘中 ChessBoard(tr+s，tc+s，dr，dc，S)；else/此棋盘中无特殊方格 /用t号骨牌覆盖左下角 Boardtr+stc+s=t；/覆盖其余方格 Chessboard(tr+s，tc+s，tr+s，tc+s，s)；.void outputBoard(int size)for int i=0;isize;i+)f

24、or int j=0;jsize;j+)；coutsetw(5)board ij;cout 递归与分治递归与分治 棋盘覆盖 /输出覆盖情况第24页，共39页，编辑于2022年，星期一252.7 合并(merge)排序算法思路算法思路:若n为1,算法终止;否则,将n个待排元素分割成k(k=2)个大致相等子集合A,B,对每一个子集合分别递归排序,再将排好序的子集归并为一个集合.初始序列a 8 4 5 6 2 1 7 3 归并到b 4 8 5 6 1 2 3 7 复制到a 4 8 5 6 1 2 3 7 归并到b 4 5 6 8 1 2 3 7 复制到a 4 5 6 8 1 2 3 7 归并到b 1

25、 2 3 4 5 6 7 8 复制到a 1 2 3 4 5 6 7 8 归并 4，5，6，8 1，2，3，7 从两个序列的头部开始归并：4与1比较，1被移到结果序列；4与2比较，2被移入结果序列4与3比较，3被放入结果序列；4和7比较，4被放入结果序列,5和7比较.，例如例如二路归并二路归并问题:将n个元素排成非递减顺序。算法设计与分析算法设计与分析 递归与分治递归与分治 合并排序合并排序第25页，共39页，编辑于2022年，星期一26 temlplate void MergeSort(Type a,int left,int right)if(1eft right)/至少有2个元素 int i

26、=(left+right)/2;/取中点 MergeSort(a,1eft,i)；MergeSort(a,i+1,right)；Merge(a,b,1eft,i,right)；/从a合并到数组b copy(a,b,left,right);/复制回数组a T(n)=d n 递归与分治递归与分治 合并排序合并排序算法如下templatevoid merge(T C,T d,int l,int m,int r)/把cl:m,cm,r归并到dl,r int:i=l,/第段的游标 j=m+1,/第二段的游标 k=l;/结果的游标 /只要段中存在i和j,则不断进行归并 while(i=m)&(j=r)if

27、 cim)for(int q=j;q=r;q+)dk+=cq；else for(int q=i;q=m；q+)dk+=cq；第26页，共39页，编辑于2022年，星期一27 MergeSort(A,N)S=1;/子数组段的长度 While(s 递归与分治递归与分治 合并排序合并排序消除递归的算法如下MergePass(X,Y,S,N)/合并大小为S的相邻的数组段I=0;while(I N-2S)/X II+S-1与X I+SI+2S-1 Y Merge(X,Y,I,I+S-1,I+2S-1);I I+2S;if(I+SN)Merge(X,Y,I,I+S-1,N-1);/S剩余元素 递归与分治递

28、归与分治 合并排序合并排序消除递归的算法如下c Lmc m+1ri ij jk kL LmmM+1M+1r rL Lr r第28页，共39页，编辑于2022年，星期一292.8 快速排序（由C.A.R.Hoare在1962年提出）算法思路:对于输入a p:r，按以下三个步骤进行排序：(1)分解:取a中的一个元素为支点(pivot)将ap:r 划分成3段:ap:q-1,aq,a q+1:r,使得 a p:q-1中任一元素aq,aq+1:r中任一元素 aq;下标q 在划分过程中确定。(2)递归求解:递归调用快速排序法分别对ap:q-1和aq+1:r 排序。(3)合并:合并a p:q-1,aq,a

29、q+1:r 为ap:r a1:8=8,4,1,7,11,5,6,9,取元素8作为支点,例如例如分解:aq=8;ap:q-1=4,1,7,5,6;aq+1:r=11,9;q=6？排序:ap:q-1=1,4,5,6,7;a q+1:r=9,11。合并:把ap:q-1中的元素放在支点元素8之前,aq+1:r中的元素放在支点元素之后,结果1,4,5,6,7,8,9,11算法设计与分析算法设计与分析 递归与分治递归与分治 快速排序快速排序第29页，共39页，编辑于2022年，星期一30快速排序算法 template void QuickSoft(Type a,int p,int r)if(pr)int

30、q=Partition(a,p,r)QuickSort(a,p,q-1);/对左半段排序 QuickSoft(a,q+1,r);/对右半段排序 templateint Partion(Type a,int p,int r)int i=p;j=r+1;type x=ap；/将=x的元素交换到右边区域/将=x的元素交换到左边区域 while(true)while(a+i x&i x)；if(i=j)break;swap(ai,aj);ap=aj；a j=x;return j Tmin(n)=O(1)n1 得:Tmin(n)=O(nlogn)复杂性复杂性分析:算法设计与分析算法设计与分析 递归与分治

31、递归与分治 快速排序快速排序 Tmax(n)=O(1)n1 得:Tmax(n)=O(n2)函数函数partitionpartition主要实现以下两个功能：主要实现以下两个功能：在在Ap.rAp.r中选择一个支点元素中选择一个支点元素pivot;pivot;对对Ap.rAp.r中的元素进行整理，使得中的元素进行整理，使得Ap.qAp.q分为两部分分为两部分Ap.qAp.q和和Aq+1.rAq+1.r，并且，并且Ap.qAp.q中的每一中的每一个元素的值不大于个元素的值不大于pivotpivot，Aq+1.rAq+1.r中的每一个元素的值不小于中的每一个元素的值不小于pivotpivot，但是但

32、是Ap.qAp.q和和Aq+1.rAq+1.r中的元素并不中的元素并不要求排好序。要求排好序。注：算法注：算法Quick_SortQuick_Sort中变量中变量q q的值一的值一定不能等于定不能等于r r，否则该过程会无限递，否则该过程会无限递归下去。归下去。第30页，共39页，编辑于2022年，星期一31随机选择支点的快速排序 template void randomizedQuickSoft(Type a,int p,int r)if(pr)int q=randomizedPartition(a,p,r)randomizedQuickSort(a,p,q-1);/对左半段排序 rando

33、mizedQuickSoft(a,q+1,r);/对右半段排序 template int randomizedPartition(Type a,int p,int r)int i=random(p,r)swap(ai,ap)return Partition(a,p,r)算法设计与分析算法设计与分析 递归与分治递归与分治 快速排序快速排序第31页，共39页，编辑于2022年，星期一32算法设计与分析算法设计与分析 递归与分治递归与分治排序算法效率比较第32页，共39页，编辑于2022年，星期一332.9线性时间选择线性时间选择定义：给定线性序列集中的定义：给定线性序列集中的n个元素和正整数个元素

34、和正整数k,1kn,求第求第k小元素的小元素的位置。位置。特别是特别是k=n/2时，怎样处理？时，怎样处理？若通过排序，复杂性为若通过排序，复杂性为O(NlogN)。能否更小？。能否更小？困扰算法界多年，最终由困扰算法界多年，最终由Rabin和和Knuth解决。解决。先看以下几种情况：先看以下几种情况：K=1求最小元素，无论采用何种方法，至少要求最小元素，无论采用何种方法，至少要N-1次比较。次比较。K=2通常的办法需要通常的办法需要(n-1)+(n-2)=2n-3次比较次比较但这不必要，因为可利用求最小元素时的信息。下面用但这不必要，因为可利用求最小元素时的信息。下面用N个叶结点的二叉树模个

35、叶结点的二叉树模拟拟N个选手两两进行淘汰比赛，最后产生冠军的过程。个选手两两进行淘汰比赛，最后产生冠军的过程。冠军要进行冠军要进行logN轮比赛，既冠军要战胜轮比赛，既冠军要战胜logN位选手。亚军一位选手。亚军一定同冠军比赛过，但不一定是最后输给冠军的那名失败者定同冠军比赛过，但不一定是最后输给冠军的那名失败者（与现实的情况有所不同）。（与现实的情况有所不同）。算法设计与分析算法设计与分析 递归与分治递归与分治 线性时间选择线性时间选择第33页，共39页，编辑于2022年，星期一34冠军冠军产生冠军若采用淘汰赛，需要进行产生冠军若采用淘汰赛，需要进行 log N轮比赛；要确保真正则是轮比赛；

36、要确保真正则是冠军要进行冠军要进行N-1次比赛。次比赛。亚军要在输给冠军的亚军要在输给冠军的 log N个选手中产生。个选手中产生。因此，求第二小元素需要因此，求第二小元素需要（N-1)+log N-1=N+log N-2次比次比较较算法设计与分析算法设计与分析 递归与分治递归与分治 线性时间选择线性时间选择第34页，共39页，编辑于2022年，星期一35问题陈述问题陈述:求求n个元素中的第个元素中的第k小元素小元素.分治算法思路分治算法思路:模仿快速排序对输入数组模仿快速排序对输入数组A进行二分划分进行二分划分,使子数组使子数组A1的元素的元素J,则则K为为A2的第的第K-J小元小元.与快速

37、排序算法不同与快速排序算法不同,它只对子数组之一进行递归处理。它只对子数组之一进行递归处理。分析分析:template Type RandomizedSelect(a,int p,int r,int k)if(p=r)return a p;int i=RandomizedPartition(a,p,r),j=i-p+l if(k 递归与分治递归与分治 线性时间选择线性时间选择第35页，共39页，编辑于2022年，星期一36最坏情况下的选择算法:通过寻找一个好的划分基数,可使最坏情况下时间为O(n).例如例如:考察如下情形:r=5,n=27,a=2,6,8,1,4,10,20,6,22,11,9

38、,8,4,3,7,8,16,11,10,8,2,14,15,1,12,5,4。算法思路(中间的中间):将a中元素分为n/r组,除最后一组外每组元素为r个.通过对每组排序找到各组的中位数,根据n/r个中位数递归使用选择算法得到支点元素.分组:2,6,8,1,4,10,20,6,22,11,9,8,4,3,7,8,16,11,10,8,2,14,15,1,12,5，4中间元集合:4,11,7,10,12,4,中间元的中间元为7,作为支点。划分:a1:11=2，6，1，4，6，4，3，2，1，5，4,a12=7,a13:27=8,10,20,22,11,9,8,8,16,1l,10,8,14,15,

39、12。若k12，则要找a13:27中第(k-12)个元素。算法设计与分析算法设计与分析 递归与分治递归与分治 线性时间选择线性时间选择第36页，共39页，编辑于2022年，星期一37templateType Select(Type a,int p,int r,int k)if (r-p75)用某个简单排序算法对数组ap:r排序；return ap+k-1；for(int i=0;i=(r-p-4)/5;i+)将ap+5*i至ap+5*i+4的第3小元素 与ap+i交换位置；/找中位数的中位数,r-p-4即上面所说的n-5 Type x=Select(a,p,p+(r-p-4)/5,(r-p-4

40、)/10);int i=Partition(a,p,r,x)，j=i-p+1;if(k1),假如j k j+m+1,则不必执行select(a,p,i,k),而返回ai，否则最后一句改为:select(a,i+m+1,r,k-j-m)算法分析:T(n)=得:T(n)=O(n)c1 n75时时,max|left|,|right|递归与分治递归与分治 线性时间选择线性时间选择第37页，共39页，编辑于2022年，星期一38算法思路:1)n较小时直接求较小时直接求(n=2).2)将将S上的上的n个点分成大致相等的个点分成大致相等的2个子集个子集S1和和S23)分别求分别求S1和和S2中的最接近点对中

41、的最接近点对*4)求一点在求一点在S1、另一点在、另一点在S2中的最近点对中的最近点对5)从上述三对点中找距离最近的一对从上述三对点中找距离最近的一对.问题描述:给定平面S上n个点,找其中的一对点,使得在n(n-1)/2个点对 中,该点对的距离最小。2.10、最接近点对问题*4)设 d=mind1,d2,d1,d2分别为s1,s2中最近点对的距离,设p1,p2分别为分割线l左右宽为d的垂直长条区域,若第三个最近 点对d 必在p1和p2中。对pp1,检查p2中满足p.y-dq.y 递归与分治递归与分治 最接近咪对问题最接近咪对问题第38页，共39页，编辑于2022年，星期一39 考察图中的14个点(d,m s1,gs2)s1中的最近点对为(b,h)其距离约为0.316.s2中最近点对(f,j),其距离为0.3,因此d=0.3.考察是否存在第三类点，p1=d,i,m，p2=g,l)。i的比较区中仅含点l。计算i和l的距离，发现它小于d，因此(i,l)是最近的点对。例例题题0.3160.3算法设计与分析算法设计与分析 递归与分治递归与分治 最接近咪对问题最接近咪对问题第39页，共39页，编辑于2022年，星期一