计算机算法分析与设计 第2章.ppt

《计算机算法分析与设计 第2章.ppt》由会员分享，可在线阅读，更多相关《计算机算法分析与设计 第2章.ppt（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第2章 递归与分治策略1 学习要点学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。2n将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出

2、其解为止。3算法总体思想n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n将求出的小规模问题

3、的解,合并为一个更大规模的问题解，自底向上逐步求出原来问题的解。4算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)5算法总体思想n

4、将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想分治法的设计思想:将一个难以直接解决的大问题，将一个难以直接解决的大问题，分割成

5、一些分割成一些规模较小的相同问题规模较小的相同问题，以便各个击破，以便各个击破，分而治之。分而治之。62.1 递归的概念n直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。n反复应用分治手段，可使子问题与原问题类型一致而其规模不断缩小，最终使子问题缩小到很容易直接求解。这自然导致递归过程的产生。n分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例7例例1 1 阶乘函数阶乘函数 阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程

6、边界条件边界条件与递归方程递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。8例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程p第n个Fibonacci数可递归地计算如下：intfibonacci(intn)if(n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)p e r m(Rn)构成。参见 P9 代码 15例5 整数划分问题p将正整数n表示成一系列正整数之和：n=n1+n2+

7、nk其中n1n2nk1，k1。p正整数n的这种表示称为正整数n的划分。p求正整数n的不同划分个数16n分析分析：前面的几个例子中，问题本身都具有比较明显的递归关系，易用递归函数直接求解。n本例若设p(n)为正整数n的划分数，则难以找到递归关系。l例如正整数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。17(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分

8、形式，即现考虑增加一个自变量：将最大加数将最大加数n1不大于不大于m的划的划分个数记作分个数记作q(n,m)。q(n,m)有如下递归关系：18(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);正整数n的划分由n1=n的划分和n1n-1的划分组成。n1=m的划的划

9、分个数分个数19q(n,m)递归关系:正整数n的划分数p(n)=q(n,n)代码见代码见P11P1120例例6 Hanoi6 Hanoi塔问题塔问题n设A,B,C是3个塔座。开始时，在A上有n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n。n问题：现要求将A上的这一叠圆盘移到B上，并仍按同样顺序叠置。p在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足规则1,2的前提下，可将圆盘移至A,B,C中任一塔座上。21在问题规模较大时，较难找到一般的解法，因此用递归技术来解决这个问题。当n=

10、1时，问题比较简单。只要将编号1的圆盘从塔座A直接移至塔座B上即可。当n1时，用塔座C作为辅助，设法将n-1个较小的圆盘从塔座A移至C，然后，将剩下的最大圆盘从塔座A移至B。再设法将n-1个较小的圆盘从塔座C移至B。22解Hanoi塔问题的递归算法如下：voidhanoi(intn,inta,intb,intc)if(n0)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、以递归地用上述方法来做。23递归小结优点：优点：结构清晰，可读性强，而且容易用结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性。数学归纳法来证明算法的正确性。因此，因此，它为设计算法、调试程序带来很大方便。它为设计算法、调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低递归算法的运行效率较低，无论是，无论是耗费的计算时间，还是占用的存储空间，耗费的计算时间，还是占用的存储空间，都比非递归算法要多。都比非递归算法要多。24解决方法：解决方法：在递归算法中在递归算法中消除递归调用消除递归调用，使其，使其转化为非递归转化为非递归算法。算法。1 1、采用一个用户定义的栈采用一个用户定义

12、的栈来模拟系统的递归调来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，归，只不过人工做了本来由编译器做的事情，优化效果不明显。优化效果不明显。2 2、用递推来实现递归函数用递推来实现递归函数。3 3、通过通过变换能变换能将一些递归转化为迭代将一些递归转化为迭代求出结果。求出结果。后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。递归小结25分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法

13、所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的该问题可以分解为若干个规模较小的相同相同问题，即该问问题，即该问题具有题具有最优子结构性质最优子结构性质因为问题的计算复杂性一般是随着问题规模的增加而增加，大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用26n利用该问题分解出的子问题的解可以合并为该问题的解；利用该问题分解出的子问题的解可以合并为该问题的解；n该问题所分解出的各个子问

14、题是相互独立的，即子问题该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。之间不包含公共的子问题。能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。27divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i

15、=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解 分治法的基本步骤实践表明，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好。28分治法的复杂性分析u分治法将规模为n的问题,分成k个规模为nm的子问题去解。u设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。u再设将原问题分解

16、为k个子问题,以及用merge将k个子问题的解合并为原问题的解,需用f(n)个单位时间。29用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：注意注意：递归方程及其解仅给出n等于m的方幂时T(n)的值，但如果T(n)足够平（光）滑，那么由n等于m的方幂时T(n)的值，可以估计对于任意整数n，T(n)的值域及增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。通过迭代法求得方程的解：30二分搜索技术 给定给定已按升序排好序已按升序排好序的的n个元素个元素a0:n-1，现要在这现要在这n个元素个元素中找出一特定元素中找出一特定元素x。

17、分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。31分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这现要在这n个元素中找个元素中找出一特定元素出一特定元素x。该问

18、题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；32n分析：比较x和a a的的中间元素中间元素amid，n若x=amid，则x在L中的位置就是mid；n如果xamid，则x在amid的后面。n无论在哪部分查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明此问题满足分治法的第二个和第三个适用条件。n该问题可以分解为若干个规模较小的相同问题;n分解出的子问题的解可以合并为原问题的解；33分析：很显然此问题分解出的子问题相互独立，即在amid的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。分解出的各个子问题是相互独立的。分

19、解出的各个子问题是相互独立的。34二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：template int BinarySearch(Type a,const Type&x,int l,int r)while(r=l)int m=(l+r)/2;if(x=am)return m;if(x 0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘,Figure(a)所示。l特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。l为将无特殊方格子棋盘转

20、化为特殊棋盘，可以用一个骨牌覆盖3个较小棋盘的会合处，如 Figure(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。l递归地使用这种分割，直至棋盘简化为棋盘11。44棋盘覆盖 第第2 2版版p18-19 p18-19 第第3 3版版 20-21 20-21 voidchessBoard(inttr,inttc,intdr,intdc,intsize)if(size=1)return;intt=tile+,/L型骨牌号s=size/2;/分割棋盘/覆盖左上角子棋盘if(drtr+s&dctc+s)/特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else/此棋盘

21、中无特殊方格/用t号L型骨牌覆盖右下角boardtr+s-1tc+s-1=t;/覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆盖右上角子棋盘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&dc=tr+s&dc=tc+s)/特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);

22、else/用t号L型骨牌覆盖左上角boardtr+stc+s=t;/覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);45复杂度分析复杂度分析T(n)=O(4k)渐进意义下的最优算法推导过程:原式等价于T(k)=4T(k-1)+1递推得:4T(k-1)=4(4T(k-2)+1)=42T(k-2)+4T(k)=42T(k-2)+4+1又有:42T(k-2)=43T(k-3)+42故T(k)=43T(k-3)+42+4+1.T(k)=4kT(0)+4k-1+4+1=O(4k)462.7 合并排序(1)(1)用分治策略进行排序用分治策略进行排序基本思想：基本思想：将元素

23、分成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,right);/复制回数组a 复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法47n解法一:原式等价于T(n)=2T(n/2)+nn递推得

24、:2T(n/2)=2(2T(n/22)+n/2)=22T(n/22)+nnT(n)=22T(n/22)+2nn又有:22T(n/22)=23T(n/23)+nn故T(n)=23T(n/23)+3nn.nT(n)=2kT(n/2k)+knn令k=logn，即n/2k=1得：nT(n)=nT(1)+nlogn=O(nlogn)复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法48n解法二:原式等价于T(n)=2T(n/2)+nn两边同除n得:n上述方程对2的幂的任意n是成立的.n递推得:n上述方程两端分别相加得:nT(n)=n+nlogn=O(nlogn)492.7 合并排序(2)

25、(2)算法mergeSortmergeSort的递归过程可以消去，P20程序。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97思想：思想：相邻元素（子数组段）两两相邻元素（子数组段）两两配对，用合并算法将其排序，直至配对，用合并算法将其排序，直至整个数组排好序。整个数组排好序。502.7 合并排序(3)(3)自然排序自然排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&最好时间复杂度：最好时间复杂度：O

26、(n)（初始已排好序）（初始已排好序）自然排序是合并排序算法的一个变形。自然排序是合并排序算法的一个变形。e.g.4,8,3,7,1,5,6,2e.g.4,8,3,7,1,5,6,21.1.用一次对初始数组的扫描找出所有已排好序的子数组段用一次对初始数组的扫描找出所有已排好序的子数组段;4,8,3,7,1,5,6,2;4,8,3,7,1,5,6,22.2.将相邻排好序的数组两两合并将相邻排好序的数组两两合并,直至完成整个数组的排直至完成整个数组的排序序.3,4,7,8,1,2,5,6,.3,4,7,8,1,2,5,6,51templatevoidQuickSort(Typea,intp,int

27、r)if(pr)intq=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序QuickSort(a,q+1,r);/对右半段排序2.8 快速排序基于分治策略的排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大（小）的记录一次就能交换到后（前）面单元，总的比较和移动次数较少。基本思想：对于输入子数组ap:r1.分解:以ap为基准元素将ap:r划分成三段ap:q-1,aq 和aq+1:r,使得ap:q-1中任一元素=aq.q在划分过程中确定.2.递归求解:分别对ap:q-1和aq+1:r进行递归排序.3.合并:将排好序的ap:q-1和aq+1:r

28、直接合并,即得ap:r.52分解并确定基准元素:templateintPartition(Typea,intp,intr)inti=p,j=r+1;Typex=ap;/将x的元素交换到右边区域while(true)while(a+ix&ix);if(i=j)break;Swap(ai,aj);ap=aj;aj=x;returnj;初始序列6,7,5,2,5,8j-;6,5,5,2,7,8i+;6,5,5,2,7,8j-;2,5,5,6,7,8i+;6,7,5,2,5,8完成5,2,5 6 7,853templateintRandomizedPartition(Typea,intp,intr)i

29、nti=Random(p,r);Swap(ai,ap);returnPartition(a,p,r);u快速排序算法的性能取决于划分的对称性。u通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。u在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)542.9 线性时间选择问题：给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。在线性时间内O（n）？

30、k=1;最小元素O(n)k=n;最大元素O(n)k=(n+1)/2:中位数O(n)?线性序集:若自然数1=2,2=3,则1=3,此称为“传递性”.另外,对于任何两个自然数1和2,或者12,或者21,或者1=2,即“三歧性”.把具有传递性和三歧性的集合称之为线性序集.55p选择问题的分治法：模仿快速排序算法，找第k小元素。p思想：对输入数组递归划分，但仅对划分出的子数组之一进行递归处理。templateTypeRandomizedSelect(Typea,intp,intr,intk)if(p=r)returnap;inti=RandomizedPartition(a,p,r),/随机产生递归划

31、分基准元素j=i-p+1;/j为ap,i中元素个数if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);/第k-j小元素在最坏情况下（找最小，但总在最大处划分），算法randomizedSelect需要O(n2)计算时间。但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。56n若能在O(n)内找到一个划分基准，使得所划分的2个子数组长度，都至少为原数组长度的倍(01)，则在最坏情况下在最坏情况下用O(n)时间完成选择任务。n例如，若=9/

32、10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。n由此可得T(n)=O(n)。57l将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。l用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。l递归调用算法select来找出这n/5个元素的中位数。l如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。选择划分基准-O(n)算法58p设所有元素互不相同p此时，找出的基准x至少比3(n-5)/10个元素大：因为在每一组中有2个元素小于本

33、组的中位数，而n/5个中位数中又有(n/5-1)/2=(n-5)/10个小于基准x。p同理，基准x也至少比3(n-5)/10个元素小。p而当n75时，3(n-5)/10n/4。所以，按此基准划分所得的2个子数组的长度都至少缩短1/4。59TypeSelect(Typea,intp,intr,intk)if(r-p75)用某个简单排序算法对数组ap:r排序;returnap+k-1;for(inti=0;i=(r-p-4)/5;i+)将ap+5*i至ap+5*i+4的第3小元素与ap+i交换位置;/找中位数的中位数，r-p-4即上面所说的n-5Typex=Select(a,p,p+(r-p-4)

34、/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k=j)returnSelect(a,p,i,k);elsereturnSelect(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之外，还有其他选择。602.10最接近点对问题n给定平面上n个点，找其中一对点，使得在n个点组成的点对中，该点对间的距离最短。n可能有多个解，

35、只找一个。n普通做法O(n2)n下界(nlogn)n寻找一个(nlogn)时间的算法?61分治：将平面上n个点的集合S分成两个子集S1和S2,每个子集约n/2个点。在S1和S2中递归地求最接近点对。但如何实现合并？若两个点分别在S1和S2中，合并过程就很复杂。u先考虑一维一维情形:S中n个点退化为x轴上的n个实数x1,x2,xn。u最接近点对即为这n个实数中相差最小的2个实数。u可以先排序，再扫描，耗时达到下界，但无法推广。假设用x轴上某个点m，将S划分为2个子集S1和S2，基于平衡子问题平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,

36、q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到能否在线性时间内找到p3,q3？62u若S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。u(m-d,m中至多包含S中的一个点。由图看出，如果如果(m-d,m中有中有S中的点，则此点就是中的点，则此点就是S1中最大点中最大点。u因此，用线性时间线性时间就能找到(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将从而我们用线性时间就可

37、以将S1的解和的解和S2的解合的解合并成为并成为S的解的解。合并步可在O(n)时间完成。u选择分割点m，使S1和S2的点大致相同。m可选为各点坐标的中位数。代码在p28，T（n）O（nlogn）63u下面来考虑二维情形选取一垂直线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对点64u考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distanc

38、e(p，q)d。满足这个条件的满足这个条件的P2中的中的点一定落在一个点一定落在一个d2d的矩形的矩形R中中u由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形矩形R中最多只有中最多只有6个个S中的点中的点。（鸽舍原理）u因此，在分治法的合并步骤中最多只需要检查最多只需要检查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，

39、v是位于同一小矩形中的2个点，则distance(u,v)d。这与d的意义相矛盾。鸽舍原理，也称“抽屉原理”或利克雷原则:原理（一）：把多于n个的元素按任一确定的方式分成n个集合，那么一定至少有一个集合中，至少含有两个元素。原理（二）：把多于mn个物体放到n个抽屉里，那么一定有一个抽屉里有m1个或者m1个以上的物体。65为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影到垂直线l上。能与p点一起构成最接近点对候选者的S2中点一定在矩形R中.它们在直线l上的投影点,距p在l上投影点的距离小于d。投影点最多只有6个若将P1和P2中所有S中点,按其y坐标排序，则对P1中所有点，对排序点列作

40、一次扫描，就可找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。66doublecpair2(S)n=|S|;if(n2)return;1、m=S中各点x间坐标的中位数;构造S1和S2；/S1=pS|x(p)m)/O(n)2、d1=cpair2(S1);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中与其距离

41、在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；/O(n)6、d=min(dm,dl);return d;优化：使用预排序对第4步优化，算法最优。复杂度分析复杂度分析T(n)=O(nlogn)672.11 循环赛日程表分治法在其他方面的应用:设计满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n(=2k)个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来

42、决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。123456782143658734127856432187655678123465872143785634128765432168课后作业课后作业n第二版习题：2-8，2-9，2-27。n第三版算法分析题：2-8，2-9，2-2769n习题习题2 28 8 对称搜索问题对称搜索问题n设n个不同的整数排好序后存于T1.n中。若存在一个下标i，1in,使得Ti=i，设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为O(logn)。n分析分析 由于n个整数是不同的，因

43、此对任意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)时间内找到所要得下标。70n习题习题2-9 有序主元素问题有序主元素问题n设T1:n是n个元素的一个数组。对任意元素，设S(x)iTix。当|S(x)|n/2时,称x为T的主元素。设计一个线性时间算法，确定T1:n是否有一个主元素。n分析分析 如果有一个主元素，则是T的中位数。反之，如果的中位数不是的主元素，则没有主元素。因此，用一个线性时间找中位数的算法可在现行时间内判定是否是一个主元素。71n习题习题2-272-27 以中位数为基准的选择问题以中位数为基准的选择问题n给定一个由n个互不相同的数组成的集合S，及一个正整数kn，试设计一个O(n)时间算法找出S中最接近S的中位数的k个数。n分析分析（1）算法设计思想 找出S的中位数median;计算T=|x-median|xS;找出T的第k小元素y;根据y找出所要的解 xS|x-median|y;72