第2章递归与分治策略 (2)优秀课件.ppt

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

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

2、9页3算法设计与分析算法设计与分析 递归与分治递归与分治如何分解？如何分解？大量实践中发现，在用分治法设计算法时，最好大量实践中发现，在用分治法设计算法时，最好使使子问题的规模大致相同子问题的规模大致相同。这种使子问题规模大。这种使子问题规模大致相等的做法是出自致相等的做法是出自一种一种平衡平衡(balancing)(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要的思想，它几乎总是比子问题规模不等的做法要好。好。子问题规模大致相同、平衡，这样最有效。通常子问题规模大致相同、平衡，这样最有效。通常 k=2.第3页，本讲稿共39页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 smaller s

4、ubinstances 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页 已知不重复且从小到大排列的已知不重复且从小到大排列的m个整数的数组个整数的数组A1.m,m=2K,K为正整数为正整数.对于给定的整数对于给定的整数c,要求找到一个下标要求找到一个下标i,使得使得Ai=c.找不到返回找不到返回0.function

5、search(c)i:=1;1 while Aic and i 递归与分治递归与分治 二分二分查找查找第6页，本讲稿共39页 算法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 b-search:=0 7算法设计与分析算法设计与分析

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

7、于方法一。算法设计与分析算法设计与分析 递归与分治递归与分治 寻找最大与最小元素寻找最大与最小元素第9页，本讲稿共39页10算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法通常，在分析算法的复杂性时，加法和乘法当作基本运算，即执通常，在分析算法的复杂性时，加法和乘法当作基本运算，即执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。硬件处理速度的常数。这个假定仅在硬件能对整数直接表示和处理时才合理。然而，在这个假定仅在硬件能对整数直接表示和处理时才合理。然而，在处理很大整数时，硬件无法

8、直接表示和处理。而用浮点数来表示处理很大整数时，硬件无法直接表示和处理。而用浮点数来表示则只能近似值，计算结果中的有效数字也受到限制。若要精确地则只能近似值，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，表示大整数并在计算结果中要求精确地得到所有位数上的数字，必须用软件方法来实现大整数的算术运算。必须用软件方法来实现大整数的算术运算。2.4 大整数的乘法算法算法问题问题:设设X,Y是两个是两个n位二进制数位二进制数,求求XY.第10页，本讲稿共39页11如何设计两个大整数的乘法运算的有效的算法？如何设计两个大整数的乘法运算的有效的算法？要求：

9、大整数超出要求：大整数超出longint表示范围，而浮点表示不精确。表示范围，而浮点表示不精确。假设：乘法时间远大于加减法、移位运算假设：乘法时间远大于加减法、移位运算将两个一位数的乘法或加法看作一步运算，那么，两个将两个一位数的乘法或加法看作一步运算，那么，两个N位数位数X*Y相乘，需要相乘，需要O(N2)时间时间算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法分治算法思路分治算法思路:若两个若两个1位数相乘或相加看作位数相乘或相加看作1步运算步运算,按传统乘法需按传统乘法需O(n2)次运算次运算.将每个将每个n(n=2K)位的二进制整数分为位的二进制整数分为2段

10、段,每段的长为每段的长为n/2位位X=A2n/2+BY=C2n/2+D。第11页，本讲稿共39页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)+O(n)计算计算XY须须4次次n/2位整数的乘法位整数的乘法,3次不超过次不超过2n位的整数加法位的整数加法,2次移位次移位(乘乘2n和乘和乘2n/2

11、).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页13算法设计与分析算法设计与分析 递归与分治递归与分治 大整数的乘法大整数的乘法 S=SIGN(X)*SIGN(Y)；X:=ABS(X)；Y:=ABS(Y)；if n=l t

12、hen 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的二进制整数，返回结果为X和Y的乘积XYfunction MULT(X,Y,n)大数相乘的分治递归算法大数相乘的分治递归算法二进制大整数乘法同样可应用于十进制大整数的乘法存放XY的符

13、号存放三个乘积算法算法第13页，本讲稿共39页142.5 2.5 矩阵相乘的矩阵相乘的StrassenStrassen法法算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法求出矩阵求出矩阵C的的n2个元素所需的时间为个元素所需的时间为0(n3)。常规算法常规算法:设矩阵设矩阵A=(aij)n n,B=(bij)n n,C=A B=(cij)n n计算计算C共需共需n n2个乘法个乘法,n2(n-1)个加法个加法.T(n)=O(n3)分治法分治法1969年，年，Strassen采用了类似于在大整数乘法中用过的分治技术，采用了类似于在大整数

14、乘法中用过的分治技术，将计算将计算2个个n阶矩阵乘积所需的计算时间改进到阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2.81)。第14页，本讲稿共39页T(2)=O(1)T(n)=8T(n/2)+O(n2)15分治算法分治算法:划分划分A,B为四个为四个n/2(n=2K)阶方阵阶方阵,则则:C11=A11B11+A12B21C12=A11B11+A12B21C21=A11B11+A12B21C22=A11B11+A12B21若若n=2,可直接计算可直接计算C;若若n2,C需需8个个n/2阶方阵的乘法和阶方阵的乘法和4个加法个加法.T(n)=得得:T(n)=O(n3)算法设计与分析算法

15、设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法第15页，本讲稿共39页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)(B11+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-(A1

16、1-A21)(B11+B12)=A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22-A21B11-A22B11-A11B11 -A11B12+A21B11+A21B12 =A21B12+A22B22算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法第16页，本讲稿共39页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，

17、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:=矩阵相乘Strassen算法算法算法17算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的StrassenStrassen法法第17页，本讲稿共39页18算法设计与分析算法设计与分析 递归与分治递归与分治 矩阵相乘的矩阵相乘的St

18、rassenStrassen法法复杂度改进为：T(n)=O(Nlog7)O(N2.81)理论意义：突破了O(N3)界限实际应用问题：递归；占用空间多；对于非2k 阶方阵的处理最好的成果：O(N2.37)继续按2*2分解。能否达到O(N2)？Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算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页(a

19、)(b)(c)(d)问题陈述问题陈述:在一个在一个2k 2k个方格组成的棋盘中个方格组成的棋盘中,恰有一方格残缺恰有一方格残缺,残缺方格的位置有残缺方格的位置有22k种。故对任何种。故对任何k0,残缺棋盘有残缺棋盘有22k种种.要要求用求用L型骨牌覆盖残缺棋盘上的所有方格且任何型骨牌覆盖残缺棋盘上的所有方格且任何2个个L型骨牌不型骨牌不得重叠覆盖得重叠覆盖。192k 2k的棋盘覆盖中，用到的棋盘覆盖中，用到的骨牌数为的骨牌数为(4k-1)/32.6 2.6 棋盘覆盖棋盘覆盖算法设计与分析算法设计与分析 递归与分治递归与分治 棋盘覆盖(a)(b)(c)(d)11 122 233 34 4455

20、5第19页，本讲稿共39页20分治算法:当k0时,将2k 2k棋盘分割为4个2k-1 2k-1子棋盘 残缺方格必位于4个子棋盘之一其余3个子棋盘中无残缺方格为此将剩余3棋盘转化为残缺棋盘.用一个L型骨牌覆盖这3个较小棋盘的结合处.这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格，原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1 1棋盘.算法设计与分析算法设计与分析 递归与分治递归与分治 棋盘覆盖第20页，本讲稿共39页21算法分析:设T(k)为覆盖2k 2k残缺棋盘的时间,当k=0时覆盖它需要常数时间O(1)当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋

21、盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k-1),T(k)=O(1)4T(k-1)+O(1)得:T(k)=(4k)与所需骨牌数同阶算法设计与分析算法设计与分析 递归与分治递归与分治 棋盘覆盖第21页，本讲稿共39页void 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页 /覆盖右上角子棋盘覆盖右上角子棋盘

22、if(dr=tc+S)/特殊方格在此棋盘中 ChessBoard(tr，tc+s，dr，dc，S)；else/此棋盘中无特殊方格 /用t号骨牌覆盖左下角 Boardtr+s-1tc+s=t；/覆盖其余方格 Chessboard(tr，tc+s，tr+s-1，tc+s，s)；./覆盖左下角子棋盘覆盖左下角子棋盘 if(dr=tr+s&dc 递归与分治递归与分治第23页，本讲稿共39页 /覆盖右下角子棋盘覆盖右下角子棋盘 if(dr=tr+s&dc=tc+S)/特殊方格在此棋盘中 ChessBoard(tr+s，tc+s，dr，dc，S)；else/此棋盘中无特殊方格 /用t号骨牌覆盖左下角 Bo

23、ardtr+stc+s=t；/覆盖其余方格 Chessboard(tr+s，tc+s，tr+s，tc+s，s)；.void outputBoard(int size)for int i=0;isize;i+)for int j=0;jsize;j+)；coutsetw(5)board ij;cout 递归与分治递归与分治 棋盘覆盖 /输出覆盖情况第24页，本讲稿共39页252.7 合并(merge)排序算法思路算法思路:若n为1,算法终止;否则,将n个待排元素分割成k(k=2)个大致相等子集合A,B,对每一个子集合分别递归排序,再将排好序的子集归并为一个集合.初始序列a 8 4 5 6 2 1

24、 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 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页，本讲稿共

25、39页26 temlplate void MergeSort(Type a,int left,int right)if(1eft right)/至少有2个元素 int i=(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

26、归并到dl,r int:i=l,/第段的游标 j=m+1,/第二段的游标 k=l;/结果的游标 /只要段中存在i和j,则不断进行归并 while(i=m)&(j=r)if cim)for(int q=j;q=r;q+)dk+=cq；else for(int q=i;q=m；q+)dk+=cq；第26页，本讲稿共39页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 Me

27、rge(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剩余元素 递归与分治递归与分治 合并排序合并排序消除递归的算法如下c Lmc m+1ri ij jk kL LmmM+1M+1r rL Lr r第28页，本讲稿共39页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 在划

28、分过程中确定。(2)递归求解:递归调用快速排序法分别对ap:q-1和aq+1:r 排序。(3)合并:合并a p:q-1,aq,a 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页30快速排序算

29、法 template void QuickSoft(Type a,int p,int r)if(pr)int 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)

30、=O(1)n1 得:Tmin(n)=O(nlogn)复杂性复杂性分析:算法设计与分析算法设计与分析 递归与分治递归与分治 快速排序快速排序 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中的每一个元中的每一个元素的值不大于素的值不大于pivotp

31、ivot，Aq+1.rAq+1.r中的中的每一个元素的值不小于每一个元素的值不小于pivotpivot，但，但是是Ap.qAp.q和和Aq+1.rAq+1.r中的元素并中的元素并不要求排好序。不要求排好序。注：算法注：算法Quick_SortQuick_Sort中变量中变量q q的值一的值一定不能等于定不能等于r r，否则该过程会无限递，否则该过程会无限递归下去。归下去。第30页，本讲稿共39页31随机选择支点的快速排序 template void randomizedQuickSoft(Type a,int p,int r)if(pr)int q=randomizedPartition(a,

32、p,r)randomizedQuickSort(a,p,q-1);/对左半段排序 randomizedQuickSoft(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页32算法设计与分析算法设计与分析 递归与分治递归与分治排序算法效率比较第32页，本讲稿共39页332.9 线性时间选择线性时间选择定义：给定线性序

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

34、可利用求最小元素时的信息。下面用N个叶结点的二叉树模拟个叶结点的二叉树模拟N个选手两两进行淘汰比赛，最后产生冠军的过程。个选手两两进行淘汰比赛，最后产生冠军的过程。冠军要进行冠军要进行logN轮比赛，既冠军要战胜轮比赛，既冠军要战胜logN位选手。亚军一定同位选手。亚军一定同冠军比赛过，但不一定是最后输给冠军的那名失败者冠军比赛过，但不一定是最后输给冠军的那名失败者（与现实的情况有所不同）。（与现实的情况有所不同）。算法设计与分析算法设计与分析 递归与分治递归与分治 线性时间选择线性时间选择第33页，本讲稿共39页34冠军冠军产生冠军若采用淘汰赛，需要进行产生冠军若采用淘汰赛，需要进行 log

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

36、元小元.与快速排序算法不同与快速排序算法不同,它只对子数组之一进行递归处理。它只对子数组之一进行递归处理。分析分析: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页36最坏情况下的选择算法:通过寻找一个好的划分基数,可使最坏情况下时间为O(n).例如例如:考察如下情形:r=5,n=27,a=2,6,8,1,4,10,20,6,22,11,9,8,

37、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,12。

38、若k12，则要找a13:27中第(k-12)个元素。算法设计与分析算法设计与分析 递归与分治递归与分治 线性时间选择线性时间选择第36页，本讲稿共39页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)/10);int i=P

39、artition(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页38算法思路:1)n较小时直接求较小时直接求(n=2).2)将将S上的上的n个点分成大致相等的个点分成大致相等的2个子集个子集S1和和S23)分别求分别求S1和和S2中的最接近点对中的最接近点对*4)求一点在求一点在S1、另一点

40、在、另一点在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页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页