《计算机算法分析与设计第2章.ppt》由会员分享，可在线阅读，更多相关《计算机算法分析与设计第2章.ppt（72页珍藏版）》请在三一办公上搜索。
1、1,第2章 递归与分治策略,2,学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。,3,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,4,算法总体思想,对
2、这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模问题的解,合并为一个更大规模的问题解，自底向上逐步求出原来问题的解。,5,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,6,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。,7,2.1 递归的概念,直接或间接地
3、调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。反复应用分治手段，可使子问题与原问题类型一致而其规模不断缩小，最终使子问题缩小到很容易直接求解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,下面来看几个实例,8,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,9,例2 Fibonacci数列无穷数列1，1，2，3，5，8，13，21
4、，34，55，称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下：int fibonacci(int n)if(n=1)return 1;return fibonacci(n-1)+fibonacci(n-2);,10,前2例中的函数都可以找到相应的非递归方式定义：,但是,有的函数却无法找到非递归定义,比如Ackerman函数.,11,例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：,12,A(n，m)的自变量m的每一个值都定义了一个单变量函数
5、：m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2,故A(n,1)=2*nm=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2n。m=3时，类似的可以推出 A(n,3)m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,13,定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。定义其拟逆函数(n)为：(n)=minkA(k)n。(n)是使nA(k)成立的最小的k值。(n)在复杂度分
6、析中常遇到。对于通常所见到的正整数n，有(n)4。理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,14,例4：排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。,设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。集合X中元素的全排列记为perm(X)。(permutation)(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。,15,R的全排列可归纳定义如下：,当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)per
7、m(Rn)构成。参见 P9 代码,16,例5 整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数,17,分析：前面的几个例子中，问题本身都具有比较明显的递归关系，易用递归函数直接求解。本例若设p(n)为正整数n的划分数，则难以找到递归关系。,例如正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。,18,(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。
8、因此，q(1,m)=1。,(1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即,现考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。q(n,m)有如下递归关系：,19,(4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分,由n1m-1 的划分和n1=m的划分组成。注意：正整数n的n1=m的所有划分形式为 m+m1+mi=n where mj m,j=1,2,i That is,m1+mi=n-m 因此，n的n1=m的划分个数是q(n-m,m),(3)q(n,n)=1+q(n,n-1);正整数
9、n的划分由n1=n的划分和n1n-1的划分组成。,n1=m的划分个数,20,q(n,m)递归关系:,正整数n的划分数p(n)=q(n,n)代码见P11,21,例6 Hanoi塔问题设A,B,C是3个塔座。开始时，在A上有n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n。问题：现要求将A上的这一叠圆盘移到B上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足规则1,2的前提下，可将圆盘移至A,B,C中任一塔座上。,22,在问题规模较大时，较难找到一般的解法，因此用
10、递归技术来解决这个问题。,当n=1时，问题比较简单。只要将编号1的圆盘从塔座A直接移至塔座B上即可。当n1时，用塔座C作为辅助，设法将n-1个较小的圆盘从塔座A移至C，然后，将剩下的最大圆盘从塔座A移至B。再设法将n-1个较小的圆盘从塔座C移至B。,23,解Hanoi塔问题的递归算法如下：,void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);,(n-1)个由A移到C借用B,编号n的圆盘由A移到B,(n-1)个由C移到B借用A,由此可见，n个圆盘的移动问题可分为2次n-1个圆盘
11、的移动问题，这又可以递归地用上述方法来做。,24,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性。因此，它为设计算法、调试程序带来很大方便。,缺点：递归算法的运行效率较低，无论是耗费的计算时间，还是占用的存储空间，都比非递归算法要多。,25,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2、用递推来实现递归函数。3、通过变换能将一些递归转化为迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,递归小
12、结,26,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质,因为问题的计算复杂性一般是随着问题规模的增加而增加，大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,27,利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,如
13、果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,28,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解,分治法的基本步骤,实践表明，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题
14、分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,29,分治法的复杂性分析,分治法将规模为n的问题,分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题,以及用merge将k个子问题的解合并为原问题的解,需用f(n)个单位时间。,30,用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：,注意：递归方程及其解仅给出n等于m的方幂时T(n)的值，但如果T(n)足够平（光）滑，那么由n等于m的
15、方幂时T(n)的值，可以估计对于任意整数n，T(n)的值域及增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。,通过迭代法求得方程的解：,31,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：,该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。,32,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,二分搜索技术,给定已按
16、升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,该问题的规模缩小到一定的程度就可以容易地解决；,33,分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xamid，则x在amid的后面。无论在哪部分查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明此问题满足分治法的第二个和第三个适用条件。该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；,34,分析：很显然此问题分解出的子问题相互独立，即在amid的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。分解出的各个子问题是相
17、互独立的。,35,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法：template int BinarySearch(Type a,const Type,算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少1/2。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。,36,大整数的乘法,设计一个算法，进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:设X和Y为n位二进制整数,X=Y=X=a 2
18、n/2+b Y=c 2n/2+d XY=ac 2n+(ad+bc)2n/2+bd,a,b,c,d,复杂度分析T(n)=O(n2)没有改进 加法移位用O(n),37,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,XY=ac 2n+(ad+bc)2n/2+bd 为了降低时间复杂度，必须减少乘法次数。XY=ac 2n+(a-b)(d-c)+ac+bd)2n/2+bdXY=ac 2n+(a+b)(d+c)-ac-bd)2n/2+bd,复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进,细节问题：两个XY的复杂度都是O(nlo
19、g3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,38,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。,39,Strassen矩阵乘法,A和B的乘积矩阵C中的元素Ci,j定义为:,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需
20、要做n次乘法和n-1次加法。因此，算出矩阵C的n2个元素所需的计算时间为O(n3),传统方法：O(n3),40,Strassen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,传统方法：O(n3)分治法:,由此可得：,复杂度分析 T(n)=O(n3)加法用O(n2),41,Strassen矩阵乘法,传统方法：O(n3)分治法:,为了降低时间复杂度，必须减少乘法的次数。,复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进,42,Strassen矩阵乘法,传统方法：O(n3)分治法:O(n2.81)更快的方法?,H
21、opcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？,43,棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。问题:用4种不同形态的L型骨牌,覆盖给定特殊棋盘上除特殊方格以外的所有方格，且任何2个不得重叠。,44,当k0时，将2k2k棋盘分
22、割为4个2k-12k-1 子棋盘,Figure(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为将无特殊方格子棋盘转化为特殊棋盘，可以用一个骨牌覆盖3个较小棋盘的会合处，如 Figure(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,45,棋盘覆盖 第2版p18-19 第3版 20-21,void chessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return;int t=tile+,/L型骨牌号 s=size/2;/分割棋盘/覆盖左上角子棋盘
23、if(dr=tc+s)/特殊方格在此棋盘中 chessBoard(tr,tc+s,dr,dc,s);else/此棋盘中无特殊方格/用 t 号L型骨牌覆盖左下角,boardtr+s-1tc+s=t;/覆盖其余方格 chessBoard(tr,tc+s,tr+s-1,tc+s,s);/覆盖左下角子棋盘 if(dr=tr+s,46,复杂度分析T(n)=O(4k)渐进意义下的最优算法,推导过程:原式等价于 T(k)=4T(k-1)+1 递推得:4T(k-1)=4(4T(k-2)+1)=42T(k-2)+4 T(k)=42T(k-2)+4+1 又有:42T(k-2)=43T(k-3)+42 故 T(k)
24、=43T(k-3)+42+4+1.T(k)=4kT(0)+4k-1+4+1=O(4k),47,2.7 合并排序(1)用分治策略进行排序,基本思想：将元素分成2个子集合，分别对子集合进行排序，最终将排好序的子集合合并为有序集合。n=1时中止。,void MergeSort(Type a,int left,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 MergeSort(a,left,i);MergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组b copy(a,b,left,r
25、ight);/复制回数组a,复杂度分析T(n)=O(nlogn)渐进意义下的最优算法,48,解法一:原式等价于 T(n)=2T(n/2)+n 递推得:2T(n/2)=2(2T(n/22)+n/2)=22T(n/22)+n T(n)=22T(n/22)+2n 又有:22T(n/22)=23T(n/23)+n 故 T(n)=23T(n/23)+3n.T(n)=2kT(n/2k)+kn 令k=logn，即n/2k=1 得：T(n)=nT(1)+nlogn=O(nlogn),复杂度分析T(n)=O(nlogn)渐进意义下的最优算法,49,解法二:原式等价于 T(n)=2T(n/2)+n 两边同除n得:
26、上述方程对2的幂的任意n是成立的.递推得:上述方程两端分别相加得:T(n)=n+nlogn=O(nlogn),50,2.7 合并排序(2),算法mergeSort的递归过程可以消去，P20程序。,思想：相邻元素（子数组段）两两配对，用合并算法将其排序，直至整个数组排好序。,51,2.7 合并排序(3)自然排序,最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)最好时间复杂度：O(n)（初始已排好序）,自然排序是合并排序算法的一个变形。e.g.4,8,3,7,1,5,6,2,1.用一次对初始数组的扫描找出所有已排好序的子数组段;4,8,3,7,1,5,6,2,2.将相邻排好序的数组
27、两两合并,直至完成整个数组的排序.3,4,7,8,1,2,5,6,52,templatevoid QuickSort(Type a,int p,int r)if(pr)int q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序,2.8 快速排序,基于分治策略的排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大（小）的记录一次就能交换到后（前）面单元，总的比较和移动次数较少。,基本思想：对于输入子数组ap:r分解:以ap为基准元素将ap:r划分成三段ap:q-1,aq 和aq+1:r,使
28、得ap:q-1中任一元素=aq.q在划分过程中确定.递归求解:分别对ap:q-1和aq+1:r进行递归排序.合并:将排好序的ap:q-1和aq+1:r直接合并,即得ap:r.,53,分解并确定基准元素:templateint Partition(Type a,int p,int r)int i=p,j=r+1;Type x=ap;/将 x的元素交换到右边区域 while(true)while(a+i x);if(i=j)break;Swap(ai,aj);ap=aj;aj=x;return j;,初始序列,54,templateint RandomizedPartition(Type a,in
29、t p,int r)int i=Random(p,r);Swap(ai,ap);return Partition(a,p,r);,快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。,最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn),55,2.9 线性时间选择,问题：给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。在线性时间内O（n）？k=1
30、;最小元素 O(n)k=n;最大元素 O(n)k=(n+1)/2:中位数 O(n)?,线性序集:若自然数1=2,2=3,则1=3,此称为“传递性”.另外,对于任何两个自然数1和2,或者12,或者21,或者1=2,即“三歧性”.把具有传递性和三歧性的集合称之为线性序集.,56,选择问题的分治法：模仿快速排序算法，找第k小元素。思想：对输入数组递归划分，但仅对划分出的子数组之一进行递归处理。,templateType RandomizedSelect(Type a,int p,int r,int k)if(p=r)return ap;int i=RandomizedPartition(a,p,r)
31、,/随机产生递归划分基准元素 j=i-p+1;/j为ap,i中元素个数 if(k=j)return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);/第k-j小元素,在最坏情况下（找最小，但总在最大处划分），算法randomizedSelect需要O(n2)计算时间。但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。,57,若能在O(n)内找到一个划分基准，使得所划分的2个子数组长度，都至少为原数组长度的倍(0 1)，则在最坏情况下用O(n)时间完成选择
32、任务。,例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。,58,将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用算法select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。,选择划分基准-O(n)算法,59,设所有元素互不相同此时，找出的基准x至少比3(n-5)/10个元素大：因为在每一组
33、中有2个元素小于本组的中位数，而n/5个中位数中又有(n/5-1)/2=(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4。所以，按此基准划分所得的2个子数组的长度都至少缩短1/4。,60,Type 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=S
34、elect(a,p,p+(r-p-4)/5,(r-p-4)/10);int i=Partition(a,p,r,x),j=i-p+1;if(k=j)return Select(a,p,i,k);else return Select(a,i+1,r,k-j);,复杂度分析T(n)=O(n),上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。,61,2.10 最接近点对问题,给定平面上n个点，找其中一对点，使得在n个点组成
35、的点对中，该点对间的距离最短。可能有多个解，只找一个。普通做法O(n2)下界(nlogn)寻找一个(nlogn)时间的算法?,62,分治：将平面上n个点的集合S分成两个子集S1和S2,每个子集约n/2个点。在S1和S2中递归地求最接近点对。但如何实现合并？若两个点分别在S1和S2中，合并过程就很复杂。,先考虑一维情形:S中n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。可以先排序，再扫描，耗时达到下界，但无法推广。,假设用x轴上某个点m，将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其
36、最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到p3,q3？,63,若S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。(m-d,m中至多包含S中的一个点。由图看出，如果(m-d,m中有S中的点，则此点就是S1中最大点。因此，用线性时间就能找到(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。合并步可在O(n)时间完
37、成。选择分割点m，使S1和S2的点大致相同。m可选为各点坐标的中位数。代码在p28，T（n）O（nlogn）,64,下面来考虑二维情形,选取一垂直线l:x=m来作为分割直线，m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。能否在线性时间内找到p,q？(n/2)2对点,65,考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的P2中的点一定落在一个d2d的矩形R中由d的意义可知，P2中任何2个S
38、中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。（鸽舍原理）因此，在分治法的合并步骤中最多只需要检查6n/2=3n个候选者,能否在线性时间内找到p3,q3？,证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)d。这与d的意义相矛盾。,鸽舍原理，也称“抽屉原理”或利克雷原则:原理（一）：把多于n个的元素按任一确定的方式分成n个集合，那么一定至少有一个集合中，
39、至少含有两个元素。原理（二）：把多于mn个物体放到n个抽屉里，那么一定有一个抽屉里有m1个或者m1个以上的物体。,66,为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影到垂直线l上。能与p点一起构成最接近点对候选者的S2中点一定在矩形R中.它们在直线l上的投影点,距p在l上投影点的距离小于d。投影点最多只有6个若将P1和P2中所有S中点,按其y坐标排序，则对P1中所有点，对排序点列作一次扫描，就可找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。,67,double cpair2(S)n=|S|;if(n m)/O(n)2、d1=cpair2(S1);
40、d2=cpair2(S2);/2T(n/2)3、dm=min(d1,d2);,4、设P1是S1中距l距离在dm之内的所有点组成的集合；P2是S2中距l的距离在dm之内所有点组成的集合；将P1和P2中点依其y坐标值排序；并设X和Y是相应的已排好序的点列；/O(nlogn)5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；/O(n)6、d=min(dm,dl);return d;优化：使用预排序对第4步优化，算法最优。,复杂度分析T(n)
41、=O(nlogn),68,2.11 循环赛日程表,分治法在其他方面的应用:设计满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n(=2k)个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,69,课后作业,第二版 习题：2-8，2-9，2-27。第三版 算法分析题：2-8，2-9，2-27,70,习题28 对称搜索问题设n个不同的整数排好序后存于T
42、1.n中。若存在一个下标i，1in,使得Ti=i，设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为O(logn)。分析 由于n个整数是不同的，因此对任意1in-1，有Ti Ti+1-1，或Ti+1Ti+1。（1）对于1in-1,当Ti i时，对任意的ijn，有 TjTi+(j-i)i+j-i=j(2)对于1in，当Tii时，对任意的1ji，有 Tj Ti-(i-j)i-i+jj 由（1）和（2）可知，用二分搜索算法可以在O(logn)时间内找到所要得下标。,71,习题2-9 有序主元素问题设T1:n是n个元素的一个数组。对任意元素，设S(x)iTix。当|S(x)|n/2时,称x为T的主元素。设计一个线性时间算法，确定T1:n是否有一个主元素。分析 如果有一个主元素，则是T的中位数。反之，如果的中位数不是的主元素，则没有主元素。因此，用一个线性时间找中位数的算法可在现行时间内判定是否是一个主元素。,72,习题2-27 以中位数为基准的选择问题给定一个由n个互不相同的数组成的集合S，及一个正整数kn，试设计一个O(n)时间算法找出S中最接近S的中位数的k个数。分析（1）算法设计思想 找出S的中位数median;计算T=|x-median|xS;找出T的第k小元素y;根据y找出所要的解 xS|x-median|y;,
