《算法设计与分析教学资料第2章》由会员分享，可在线阅读，更多相关《算法设计与分析教学资料第2章（150页珍藏版）》请在金锄头文库上搜索。
1、第2章 递归与分治策略 学习要点学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。分治法概述n分治法是一种非常有用的算法技术，它可以用于求解许多算法问题.n什么是分治法?算法总体思想n计算机求解的复杂度与问题的规模有关，回忆：a)1、2、3n个元素的排序问题；b)1、2、3n个元素的查找问题；n结论：多个元素的排序和查找比较少元素的排序和查找复杂和困难的多！n想法：能否将“多个元素的
2、排序和查找”变成数个“较少元素的排序和查找”，分别进行？算法总体思想n分治法的可行性：如果原问题可以分成k个子问题且子问题都可解并可利用子问题的解求出原问题的解算法总体思想问题分解是求解复杂问题时很自然的做法。求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。n将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规
3、模足够小，很容易求出其解为止。算法总体思想n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)
4、=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想是，将一个难以直接解决的大问题，分治法的
5、设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。 凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法算法总体思想通常，由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。由此可知，分治法求解很自然地可用一个递归过程来表示。分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。2.1 递归的概念n直接或间接地
6、调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。n分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。2.1 递归的概念n递归的使用场合：数据结构本身是递归定义的，其实现算法往往是递归算法，比如二叉树和图等；求解过程需要递归，算法描述简捷其易于理解及分析，比如阶乘计算下面来看几个实例。n在算法设计中使用递归技术，往往使
7、算法的描述简单明了、易于理解、容易编程和验证。在计算机软件领域，递归算法是一种非常重要并且不可或缺的算法。2.1 递归的概念例例1 1 阶乘函数阶乘函数 阶乘函数可递归地定义为：边界条件：边界条件：非递归定义非递归定义的初始值的初始值递归方程：递归方程：递归定义式递归定义式边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。较小自变量的函较小自变量的函数值表示较大自数值表示较大自变量的函数值变量的函数值2.1 递归的概念例例1 1 阶乘函数阶乘函数 第n个阶乘可递归地计算如下：intfactorial(int n) if (n=0) return
8、1; return n*factorial(n-1);2.1 递归的概念例例2 Fibonacci2 Fibonacci数列（数列（斐波那契数列）无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：intfibonacci(intn)if(n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 2.1 递归的概念例例4 4 排列问题排列问题(http:/ perm(R): (r1)perm(R1) (r2)perm(
9、R2) 即： (r1)(r2) (r2)(r1)当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 n=3 perm(R): (r1)perm(R1) (r2)perm(R2) (r3)perm(R3) 即：(r1) perm(R2R3) (r2)perm(R1R3) (r3)perm(R1R2)最终：(r1)(r2)（r3) (r1)(r3)(r2) (r2)(r1)(r3) (r2)(r3)(r1) (r3)(r1)(r2) (r3)(r2)(r1) 2.1 递归的概念
10、例例4 4 排列问题排列问题/perm函数：perm(Objectlist,intk,intm)/作用：输出数组list中，前缀为顺序的前k个元素，后缀为后m-k个元素的全排列，所组成的排列/参数：list数组，要进行排列的元素/k，数组下标0-（k-1）为前缀/m，数组下标0-m为要进行排列的元素/说明：若要对list中的所有元素进行排列，k应为0，m应为数组上界2.1 递归的概念例例4 4 排列问题排列问题publicstaticvoidperm(Objectlist,intk,intm)/若所有要排列元素都为前缀，则依次输出if(k=m)for(inti=0;i=m;i+)System.
11、out.print(listi+);System.out.println();/否则，前缀增1，后缀减1else/依次将原后缀中任一个元素放入到前缀中，得到新的前后缀，进行递归for(inti=k;i=m;i+)swap(list,k,i);perm(list,k+1,m);swap(list,k,i);2.1 递归的概念例例4 4 排列问题排列问题publicstaticvoidswap(Objectlist,intk,intm)Objectt;t=listk;listk=listm;listm=t;intmain()intlist=1,2,3;perm(list,0,2);return0;
12、2.1 递归的概念例例4 4 排列问题排列问题作业2：采用递归方式实现排列问题排列问题2.1 递归的概念例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数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。2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数
13、直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。注意：m的取值范围为1,)，我们可分段讨论。m=11mn(2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。(3) q(n,n)=1+q(
14、n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将
15、最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。n6；n5+1；n4+2，4+1+1；n3+3，3+2+1，3+1+1+1；n2+2+2，2+2+1+1，2+1+1+1+1；n1+1+1+1+1+1。例：例：例：例：q(6,3)=q(3,3)+q(6,2)q(6,3)=q(3,3)+q(6,2)2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m
16、)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。 2.1 递归的概念例例5 5 整数划分问题整数划分问题/函数：函数：q(int n,int m)/作用：用来得到正整数作用：用来得到正整数n，最大加数不大于，最大加数不大于m的划分个数的划分个数public static int q(int n,int m)/若正整数或最大加数小于若正整数或最大加数小于1，则返回，则返回0if(n1|m1) return 0;/若正整数或最大加数等于若正整数或最大加数等于1，则划分个数为，则划分个数为1（n个个1相加）相加）if(n=1|m=1) return 1;/若最大加数实
17、际上不能大于正整数若最大加数实际上不能大于正整数n，若大于则划分个数等于最大加数为，若大于则划分个数等于最大加数为n的的划分个数划分个数if(n0)hanoi(n-1,a,c,b);/在移动过程中，以塔座c作为辅助塔座move(a,b);/将塔座a上编号为n的圆盘移至塔座b上hanoi(n-1,c,b,a);2.1 递归的概念例例6 Hanoi6 Hanoi塔问题塔问题作业4：画图表示HanoiHanoi塔问题塔问题关键：为算法建立递归调用工作栈2.1 递归的概念通常，在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事：（1）将所有实参指针、返回地址等信息传递给被调用算法；（2
18、）为被调用算法的局部变量分配存储区；（3）将控制转移到被调用算法的入口。在从被调用算法返回调用算法时，系统也相应地要完成三件事：（1）保存被调用算法的计算结果；（2）释放分配给被调用算法的数据区；（3）依照被调用算法保存的返回地址将控制转移到调用算法。系统在实现子程序的调用时, 要用栈方式管理调用子程序时的返回地址。子程序调用的内部实现为两个方面。2.1 递归的概念当有多个算法构成嵌套调用时，按照后调用先返回的原则进行。注意：信息传递和控制转移必须通过栈来实现。重要的是数据栈和工作栈。递归算法的实现类似于多个算法的嵌套调用，只不过调用算法和被调用算法是同一个算法。为了保证递归调用正确执行，系统
19、要建立一个递归调用工作栈，为各层次的调用分配数据存储区。一个递归过程的执行类似于多个子程序的嵌套调用, 递归过程是自己调用自己本身代码。如果把每一次的递归调用视为调用自身代码的复制件, 则递归实现过程基本上和一般子程序的实现相同。递归小结优点：优点：结构清晰，可读性强，而且容易用结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。为设计算法、调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比耗费的计算时间还是占用的存储空间都比非递归
20、算法要多。非递归算法要多。解决方法：解决方法：在递归算法中在递归算法中消除递归调用消除递归调用，使其，使其转化为转化为非递归算法非递归算法。1 1、采用一个用户定义的栈来模拟系统的递归调、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，归，只不过人工做了本来由编译器做的事情，优化效果不明显（优化效果不明显（常用方法！常用方法！）。）。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过、通过变换能变换能将一些递归转化为尾递归，从而将一些递归转化为尾递归，从而迭代求出结果。
21、迭代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。递归小结讨论：n找出n个自然数(1,2,.,n)中取r个数的组合。ninta100;nvoidcomb(intm,intk)nfor(inti=m;i=k;i-)nak=i;nif(k1)ncomb(i-1,k-1);nelsenfor(intj=a0;j0;j-)ncoutaj;ncoutendl;nnnnintmain()nintn=5,r=3;na0=r;ncomb(n,r);nn=5n=5，r=3r=3时，从大到小时，从大到小时，从大到小时，从大到小排列的组合
22、数为：排列的组合数为：排列的组合数为：排列的组合数为：5 4 35 4 35 4 25 4 25 4 15 4 15 3 25 3 25 3 15 3 15 2 15 2 14 3 24 3 24 3 14 3 14 2 14 2 13 2 13 2 1分治法的基本思想基本基本思想思想n当要求解一个输入规模n相当大的问题时，直接求解往往是非常困难的，甚至没法求出。正确的方法是, 首先应仔细分析问题本身所具有的特性，然后根据这些特性选择适当的设计策略来求解。n在将这n个输入分成k个不同子集合的情况下，如果能得到k个不同的可独立求解的子问题，而且在求解之后，还可找到适当的方法把它们合并成整个问题的
23、解，那么，可考虑使用分治法来求解。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质n利用该问题分解出的子问题的解可以利用该问题分解出的子问题的解可以合并合并为该问题的为该问题的解；解；n该问题所分解出的各个子问题是该问题所分解出的各
24、个子问题是相互独立的相互独立的，即子问，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。边界条件：边界条件：非递归定义非递归定义的初始值
25、的初始值递归方程：递归方程：递归定义式递归定义式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); /将各子问题的解合并为原问题的解 分治法的基本步骤人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法
26、是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的复杂性分析（了解）一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(
27、n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。主定理n注意：主定理的三种情况并没有覆盖所有f(n)，存在某些f(n)不满足以上任何一种情况的条件，则此时就不能用主方法求解递推试。n采用分治法求解问题通常得到一个递归算法，分析相应算法的时间复杂性，往往可得到如下的递归式：T(n)=kT(n/m)+cnb,T(1)=cn显然可以直接使用主方法得到如下定理：例：nT(n)=16T(n/4)+nnT(n)=T(3n/7)+1nT(n)=7T(n/2)+n2分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否
28、在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。二分搜索技术（回忆查找算法）给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分
29、析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法（二分搜索算法（注意：注意：C+C+程序！程序有问题程序！程序有问题吗？吗？）：templateint
30、BinarySearch(Typea,constType&x,intl,intr)while(r=l)intm=(l+r)/2;if(x=am)returnm;if(xam)r=m-1;elsel=m+1;return-1;算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . =
31、 an-1 中搜索 x / 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x二分搜索技术大整数的乘法 考虑考虑计算机组成原理计算机组成原理课程中关于基本运算的说法：课程中关于基本运算的说法：1.1.加法和乘法是基本运算，加法和乘法是基本运算，WhyWhy? ?2.2.减法和除法如何实现？减法和除法如何实现？3.3.如果实现加法和乘法的计算数超过了机器表示的范围，如果实现加
32、法和乘法的计算数超过了机器表示的范围，How How to doto do? ?4.4.精确表示运算时，必须用软件来实现！精确表示运算时，必须用软件来实现！大整数运算面临的问题：大整数运算面临的问题：（1 1）直接以整数运算，可能超出硬件整数表示范围。）直接以整数运算，可能超出硬件整数表示范围。（2 2）若以浮点数表示，不能精确的表示大整数及其运算结）若以浮点数表示，不能精确的表示大整数及其运算结果。果。所以，采用某种算法来实现大整数运算是非常必要的。所以，采用某种算法来实现大整数运算是非常必要的。大整数（二进制整数）的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个
33、n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法（a、b、c、d分段均为n/2位！并假设n为2的幂数！）:X=Y=X=a2n/2+bY=c2n/2+d(why?)XY=ac2n+(ad+bc)2n/2+bd（式1）abcd复杂度分析复杂度分析T(n)=O(n2) 没有改进没有改进将每2个1位数的乘法或加法看作一步运算关键：减少乘法次数！大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法:一种改进方法XY=ac2n+(ad+bc)2n/2+bd为
34、了降低时间复杂度，必须减少乘法的次数。1.XY=ac2n+(a-c)(b-d)+ac+bd)2n/2+bd（式3）2.XY=ac2n+(a+c)(b+d)-ac-bd)2n/2+bd（式4）复杂度分析复杂度分析T(n)=O(nlog3)=O(n1.59) 较大的改进较大的改进递归方程组解的渐进阶的求法递归方程组解的渐进阶的求法套用公式法套用公式法细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。大整数的乘法大整数的乘法大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进
35、行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法:O(n1.59) 较大的改进u更快的方法?如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法。http:/ 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3)u传统方法：O(n3)Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一
36、矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3)（式2）（式3）（式4）（式5）关键：减少乘法次数！Strassen矩阵乘法u传统方法：O(n3)u分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81) 较大的改进较大的改进Strassen矩阵乘法Strassen矩阵乘法u传统方法：O(n3)u分治法:O(n2.81)u更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘
37、法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法？棋盘覆盖在一个2k2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。棋盘覆盖在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。问题：在任何一个问题：在任何一个2k2k的棋盘覆盖的棋盘覆盖中，用到的中，用到的L型骨牌个数是多少？型骨牌个数是多少？
38、（4k-1）/3个！棋盘覆盖考虑：使用分治策略，求解棋盘覆盖问题当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。 dcdrtrtcsize棋盘覆盖问题中的数据结构棋盘覆盖问题中的数据结构棋盘覆盖问题publicclassChessprivateintboard;/用来表示棋盘privateintboardSize;
39、/表示棋盘的大小为2的多少次方privateintdr,dc;/棋盘中特殊方格的位置（行号、列号）privateinttile;/骨牌标号publicChess()board=newint11;dr=0;dc=0;boardSize=0;publicChess(intr,intc,ints)intn;n=(int)Math.pow(2,s);if(n=r|n=c)System.out.println(初始化参数错误！);elseboard=newintnn;dr=r;dc=c;boardSize=s;publicvoidPrint()for(inti=0;iMath.pow(2,this.bo
40、ardSize);i+)for(intj=0;jMath.pow(2,this.boardSize);j+)System.out.print(String.format(%3d|,this.boardij);System.out.println();publicstaticvoidmain(Stringargs)Chessc1=newChess(3,4,3);c1.chessBoard(0,0,c1.dc,c1.dr,(int)Math.pow(2,c1.boardSize);c1.Print();/函数参数说明：/tr：棋盘左上角方格的行号；/tc：棋盘左上角方格的列号；/dr：特殊方格所在
41、的行号；/dc：特殊方格所在的列号；/size：2k,棋盘规格为2k2k。publicvoidchessBoard(inttr,inttc,intdr,intdc,intsize)if(size=1)return;intt=tile+,s=size/2;/t:L型骨牌号,s分割棋盘/覆盖左上角子棋盘if(drtr+s&dctc+s)/特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else/此棋盘中无特殊方格则用t号L型骨牌覆盖右下角boardtr+s-1tc+s-1=t;/覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆盖右上角子棋盘
42、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=tr+s&dc=tc+s)/特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);elseboardtr+stc+s=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);棋盘覆盖voidchessBoard(inttr,inttc,intdr,intdc,intsi
43、ze)if(size=1)return;intt=tile+,/L型骨牌号s=size/2;/分割棋盘/覆盖左上角子棋盘if (drtr+s&dctc+s)/特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else/此棋盘中无特殊方格/用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-1t
44、c+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);else/用t号L型骨牌覆盖左上角boardtr+stc+s=t;/覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);复杂度分析复杂度分析T(n)=O(4k)渐进意义下的最优算法棋盘覆盖1.其中用一个二维整型数组board表示棋盘。2.Board00是棋盘的左上角方格。3.Tile是算法中的一个全局整型变量，用来表示L型骨
45、牌的编号，其初始值为0。4.算法的输入参数是：tr:棋盘左上角方格的行号tc:棋盘左上角方格的列号dr:特殊方格所在的行号dc:特殊方格所在的列号size:size=2k 棋盘规格为2k2k 棋盘覆盖棋盘覆盖棋盘覆盖棋盘覆盖棋盘覆盖棋盘覆盖棋盘覆盖棋盘覆盖棋盘覆盖合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。voidMergeSort(Typea,intleft,intright)if(leftright)/至少有2个元素inti=(left+right)/2;/取中点mergeSort(a,l
46、eft,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组bcopy(a,b,left,right);/复制回数组a合并排序算法是用分治策略实现对n个元素进行排序的算法http:/zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法publicstaticvoidmergeSort(Comparablea,intleft,intright)if(leftright)/至少有2个元素inti=(left+r
47、ight)/2;/取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组bcopy(a,b,left,right);/复制回数组a合并排序voidmergesort(inta,intleft,intright)intb100;if(leftright)inti=(left+right)/2;mergesort(a,left,i);mergesort(a,i+1,right);merge(a,b,left,i,right);/合并两个排好序的数组段到一个新的数组b中Copy(a,b,left,rig
48、ht);/将合并后的数组段再复制回数组a中合并排序voidmerge(intc,intd,intl,intm,intr)inti=l,j=m+1,k=l;while(i=m)&(j=r)if(cim)for(intq=j;q=r;q+)dk+=cq;elsefor(intq=i;q=m;q+)dk+=cq;/merge可在时间内完成voidCopy(inta,intb,intm,intn)for(inti=m;in;while(n!=0)cinm;for(inti=0;iai;mergesort(a,0,m-1);for(intj=0;jm;j+)coutaj;coutendl;n-;retu
49、rn0;合并排序算法mergeSort的递归过程可以消去。（回忆上学期的方法）初始序列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合并排序合并排序合并排序合并排序/合并排序的非递归算法/对数组a中的所有元素进行合并排序publicstaticvoidmergeSort(Comparablea)Comparableb=newComparablea.length;ints=1;/合并的有序数组段的初始大小/有序数组段的长度小于数组长度继续合并while(sa.len
50、gth)/从下界开始将a中的相邻的长度为s的元素合并排序到b中mergePass(a,b,s);s+=s;/待合并的有序数组段的长度增加一倍mergePass(b,a,s);s+=s;/待合并的有序数组段的长度增加一倍/合并大小为s的相邻子数组/从数组下界开始，将数组x中相邻的长度为s的数组段合并排序到y中publicstaticvoidmergePass(Comparablex,Comparabley,ints)inti=0;while(i=x.length-2*s)/合并大小为s的相邻2段子数组xi:i+s-1和xi+s:i+2*s-1merge(x,y,i,i+s-1,i+2*s-1);
51、i=i+2*s;/剩下的元素个数小于2s，大于sif(i+sx.length)/合并数组段xi:i+s-1和xi+s:x.length-1merge(x,y,i,i+s-1,x.length-1);/剩下的元素的个数小于selse/直接将xi:x.length-1复制到yfor(intj=i;jx.length;j+)yj=xj;合并排序自然合并排序是合并排序算法的一种改进.一般的合并排序算法中，第一步合并相邻长度为1的子数组段，因为长度为1的子数组段是已经排好序的。自然合并排序:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为4,8,3,7,1,5,
52、6,2,则自然排好序的子数组段有4,8,3,7,1,5,6,2.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段(3,4,7,8,1,2,5,6).继续合并相邻排好序的子数组段,直至整个数组已排好序.考虑：合并排序、自然合并排序的时间复杂度？合并排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录
53、每次移动的距离较大，因而总的比较和移动次数较少。templatevoidQuickSort(Typea,intp,intr)if(pr)intq=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序QuickSort(a,q+1,r);/对右半段排序快速排序算法是基于分治策略的另一排序算法（回忆上学期的方法）http:/zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#Javahttp:/ 7, 5, 2, 5, 8j-;5, 7, 5, 2, 6, 8i+;5, 6, 5, 2, 7, 8j
54、-;5, 2, 5, 6, 7, 8i+;完成6, 7, 5, 2, 5, 85, 2, 5 6 7, 8Partition以一个确定的基准元素以一个确定的基准元素ap对子数组对子数组ap:r进行划分进行划分快速排序快速排序算法基本思想是：对输入的子数组ap:r，按以下三个步骤进行排序。（1）分解（Divide）：以ap为基准元素将ap:r划分成3段ap:q-1,aq和aq+1:r,使得ap:q-1中任何一个元素小于等于aq,而aq+1:r中任何一个元素大于等于aq。下标q在划分过程中确定。（2）递归求解（Conquer）：通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。（3
55、）合并（Merge）：由于对ap:q-1和aq+1:r的排序是就地进行，所以在ap:q-1和aq+1:r都已排好的序后，不需要执行任何计算，ap:r就已排好序。/qSort函数：对数组ap:r进行快速排序privatestaticvoidqSort(Comparablea,intp,intr)if(pr)intq=partition(a,p,r);qSort(a,p,q-1);qSort(a,q+1,r);/对ap:r以ap的值为基准进行分割，得到基准元素的位置q/对分割以后的前半部分进行快速排序/对分割以后的后半部分进行快速排序上述算法的关键是使用partition对数组进行划分，其主要代码
56、为：privatestaticintpartition(Comparablea,intp,intr)inti=p,j=r+1;Comparablex=ap;while(true)while(a+pareTo(x)0&i0);if(i=j)break;swap(a,i,j);ap=aj;aj=x;returnj;例如：以下序列的划分过程5，2，6，4，9，2，10，405，2，6，4，9，2，10，415，2，4，4，9，2，10，615，2，4，4，9，2，10，625，2，4，4，2，9，10，625，2，4，4，2，9，10，632，2，4，459，10，63partition算法需要注意
57、的细节：（1）保证i，j不出现下标越界i不断增加，j不断减小，所以i可能超出数组段上界，j可能超出数组段下界，而由于比较元素处于数组段下界位置，可作为哨兵保证j不超出下界，所以对于i增加i1;T(n)=0(1)n=1;T（n）=O(n2)；最好情况下，每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域。T(n)=O(1)n1T（n）=O(nlogn)。可证：快排在平均情况下的时间复杂度也是O(nlogn)。templateintRandomizedPartition(Typea,intp,intr)inti=Random(p,r);Swap(ai,ap);returnPar
58、tition(a,p,r);快速排序快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。快速排序templatevoidRandomizedQuickSort(Typea,intp,intr)if(pr)intq=RandomizedPartition(a,p,r);RandomizedQuickSort(a,p,q-1);/对左半段排序RandomizedQuickSort(a,
59、q+1,r);/对右半段排序&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)基于随机选择策略的划分算法：privatestaticintrandomizedPartition(Comparablea,intp,intr)inti=random(p,r);swap(a,r,p);returnpartition(a,p,r);/randomizedQuickSort随机化的快速排序算法privatestaticvoidrandomizedQuickSort(Comparablea,intp,intr)if
60、(pr)intq=randomizedPartition(a,p,r);randomizedQuickSort(a,p,q-1);randomizedQuickSort(a,q+1,r);线性时间选择考虑：在快速排序中，可以发现，算法的效率与基准元素的选择有关！讨论：设计一个算法，找出数组a0:n-1中元素的最大和最小值。给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为要找的元素。当k=1时，则要找最小元素；当k=n时，则要找最大元素当k=(n+1)/2时，则要找中位数。线性时间选择在某些特殊情况下，很容
61、易设计出解选择问题的线性时间算法。如：当要选择最大元素或最小元素时，显然可以在O(n)时间完成。一般的选择问题，特别是中位数的选择问题似乎比最小（大）元素要难。但实际上，从渐近阶的意义上，它们是一样的。也可以在O(n)时间完成。下面讨论解一般的选择问题的分治算法randomizedSelect线性时间选择算法思想（与快速排序算法类似）：（1）以随机元素为基准对集合进行划分。（2）判断要查找元素在划分的那一部分，然后对该部分进行递归查找。templateTypeRandomizedSelect(Typea,intp,intr,intk)if(p=r)returnap;inti=Randomize
62、dPartition(a,p,r),j=i-p+1;if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。privatestaticComparablerandomizedSelect(Comparablea,intp,intr,intk)if(p=r)returnap;inti=randomizedPartition
63、(a,p,r),j=i-p+1;if(k=j)returnai;if(kj)returnrandomizedSelect(a,p,i-1,k);elsereturnrandomizedSelect(a,i+1,r,k-j);线性时间选择如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下在最坏情况下用O(n)时间完成选择任务。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O
64、(n)。第2种算法：例子n按递增顺序，找出下面29个元素的第18个元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.n(1)把前面25个元素分为5(=floor(29/5)组；(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7).n(2)提取每一组的中值元素，构成集合31,49,13,25,16；n(3)递归地使用算法求取该集合的中值，得到m=25；n(4)根据m=25,把2
65、9个元素划分为3个子数组：P=8,4,11,3,13,6,19,16,5,7,23,22Q=25R=31,60,33,51,57,49,35,43,37,52,32,54,41,46,29线性时间选择例子（续）n(5)由于|P|=13,|Q|=1,k=18，所以放弃P,Q，使k=18-13-1=4，对R递归地执行本算法；n(6)将R划分成3(floor(18/5)组：31,60,33,51,57,49,35,43,37,52,32,54,41,46,29n(7)求取这3组元素的中值元素分别为：51,43,41，这个集合的中值元素是43;n(8)根据43将R划分成3组：31,33,35,37,3
66、2,41,29,43,60,51,57,49,52,54,46线性时间选择例子（续）n(9)因为k=4，第一个子数组的元素个数大于k，所以放弃后面两个子数组，以k=4对第一个子数组递归调用本算法；n(10)将这个子数组分成5个元素的一组：31,33,35,37,32，取其中值元素为33；n(11)根据33，把第一个子数组划分成31,32,29,33,35,37,41;n(12)因为k=4,而第一、第二个子数组的元素个数为4，所以33即为所求取的第18个小元素。线性时间选择l将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出
67、每组的中位数，共n/5个。l递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。线性时间选择设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。划分策略示意图：白色圆点：每组的中位数点x：中位数的中位数比x小的元素至少3(n-5)/10个比x大的元素至少3(n-5
68、)/10个而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。TypeSelect(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)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k=j)returnSelect(
69、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之外，还有其他选择。Select的计算时间复杂性T(n)：设数组长度为n当n75时，算法select所用的计算时间不超过某一常数C1当n75时，for循环执行n/5次，每次用时为某一常数；select找中位数的中位数，由于长度为原长度的1/5，所以用时可记为T(n/5)；划分
70、以后所得到数组至多有3n/4个元素，用时记为T(3n/4)。所以T(n)可以递归表示为：复杂度分析复杂度分析T(n)=O(n)上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。privatestaticComparableselect(Comparablea,intp,intr,intk)if(r-p5)bubbleSort(a,p,r);returnap+k-1;for(inti=0;i=(r-p-4)/5;i+)in
71、ts=p+5*i,t=s+4;for(intj=0;j3;j+)for(intn=s;n0)swap(a,p+i,s+2);Comparablex=select(a,p,p+(r-p-4)/5,(r-p+6)/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);n问题的提出给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对的距离最小。最直接的方法：将每一个点与其他n-1个点的距离计算出来，找出最小距离的2点。效率太低，需要O(n2)的计算
72、时间已经证明，该算法的计算时间下界是(nlogn)。最接近点对问题寻找效率更高的方法：(nlogn)时间算法分治法：将n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归的求最接近点对。问题：如何将求出的子集的最接近点对合并为原集合的最接近点对。最接近点对问题n为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。n一个简单的办法是先把x1,x2,xn排好序，再进行一次线性扫描就可以找出最接近点对，T(n)=O(nlogn)。然而这种方法无法推广到二维情形。最接近点对
73、问题最接近点对问题假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到能否在线性时间内找到p3,q3？最接近点对问题u如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3 (m-d,m，q3 (m,m+d。u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必
74、有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果如果(m-d,m中有中有S中的点，则此点就是中的点，则此点就是S1中最大点。中最大点。u因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将从而我们用线性时间就可以将S1的解和的解和S2的解合并成为的解合并成为S的解的解。能否在线性时间内找到能否在线性时间内找到p3,q3？n分割点m的选取不当，会造成|S1|=1，|S2|=n-1的情形，使得：T(n)=T(n-1)+O(n)=O(n2)n这种情形可以通过“平衡子问题”方法加以解决：选
75、取各点坐标的中位数作分割点。最接近点对问题由此，求一维点集S的最接近点对的算法为：publicstaticdoublecpair1(S)n=|S|;if(n2)return;m=S中各点坐标中位数;构造S1和S2;/S1=x|xmd1=cpair1(S1);d2=cpair1(S2);p=max(S1);q=min(S2);d=min(d1,d2,q-p);returnd;复杂度分析复杂度分析T(n)=O(nlogn)最接近点对问题最接近点对问题u下面来考虑二维的情形。设S中的点为平面上的点，它们都有两个坐标值x和y。选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将
76、S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。能否在线性时间内找到能否在线性时间内找到p,q？最接近点对问题u考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的满足这个条件的P2中的中的点一定落在一个点一定落在一个d2d的矩形的矩形R中中u由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形矩形R中最多只有中最多只有6个个S中的点中的点。u因此，在分治法的合并步骤中最多只需要检查最多只需要检查6n/2=
77、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的意义相矛盾。为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多
78、只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。最接近点对问题最接近点对问题doublecpair2(S)n=|S|;if(n2)return;1、m=S中各点x间坐标的中位数;构造S1和S2；/S1=pS|x(p)m2、d1=cpair2(S1);d2=cpair2(S2);3、dm=min(d1,d2);4、设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；将P1和P2中点依其y坐
79、标值排序；并设X和Y是相应的已排好序的点列；5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；6、d=min(dm,dl);returnd;复杂度分析复杂度分析T(n)=O(nlogn)分析算法的时间复杂性T(n)：第1步和第5步用了O(n)时间；第3步和第6步用了O(1)时间；第2步用了2T(n/2)时间；第4步每次执行排序要用O(nlogn)时间，可以采用预排序技术，在使用分治法之前，将S中n个点依其y值排序得到有序序列P*，以后
80、执行第4步只需对P*做一次线性扫描，即可得到点列X和Y，然后第5步对X做一次线性扫描，即可得到dl，所以第4步和第5步共用了O(n)时间。复杂度分析复杂度分析T(n)=O(nlogn)最接近点对问题n问题提出：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n-1天。按此要求，可以将比赛日程表设计成n行n-1列的表格，i行j列表示第i个选手在第j天所遇到的选手。循环赛日程表循环赛日程表按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛
81、日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。1234567821436587341278564321876556781234658721437856341287654321 显然，这个求解过程是自底向上的迭代过程，其中左上角显然，这个求解过程是自底向上的迭代过程，其中左上角和左下角分别为选手和左下角分别为选手1至选手至选手4以及选手以及选手5至选手至选手8前前3天的比赛天的比赛日程，据此，将左上角部分的所有数字按其对应位置抄到右下日程，据此，将左上角部分的所有数字按其对应位置抄到右下角，将左下角的所有数字按其对
82、应位置抄到右上角，这样，就角，将左下角的所有数字按其对应位置抄到右上角，这样，就分别安排好了选手分别安排好了选手1至选手至选手4以及选手以及选手5至选手至选手8在后在后4天的比赛天的比赛日程，如图日程，如图(c)所示。具有多个选手的情况可以依此类推。所示。具有多个选手的情况可以依此类推。 (b) 2k(k=2)个选手比赛个选手比赛 (c) 2k(k=3)个选手比赛个选手比赛加加4加加2(a) 2k(k=1)个选手比赛个选手比赛12211 22 13 44 33 44 31 22 11 2 3 42 1 4 33 4 1 24 3 2 15 6 7 86 5 8 77 8 5 68 7 6 55
83、 6 7 86 5 8 77 8 5 68 7 6 51 2 3 42 1 4 33 4 1 24 3 2 1 这这种种解解法法是是把把求求解解2k个个选选手手比比赛赛日日程程问问题题划划分分成成依依次次求求解解21、22、2k个个选选手手的的比比赛赛日日程程问问题题，换换言言之之，2k个个选选手手的的比比赛赛日日程程是是在在2k-1个个选选手手的的比比赛赛日日程程的的基基础础上上通通过过迭迭代代的的方方法法求得的。在每次迭代中，将问题划分为求得的。在每次迭代中，将问题划分为4部分：部分：（1）左上角：左上角为）左上角：左上角为2k-1个选手在前半程的比赛日程；个选手在前半程的比赛日程；（2）
84、左左下下角角：左左下下角角为为另另2k-1个个选选手手在在前前半半程程的的比比赛赛日日程程，由由左左上上角角加加2k-1得得到到，例例如如22个个选选手手比比赛赛，左左下下角角由由左左上上角角直直接接加加2得到，得到，23个选手比赛，左下角由左上角直接加个选手比赛，左下角由左上角直接加4得到；得到；（3）右右上上角角：将将左左下下角角直直接接抄抄到到右右上上角角得得到到另另2k-1个个选选手手在在后后半程的比赛日程；半程的比赛日程；（4）右右下下角角：将将左左上上角角直直接接抄抄到到右右下下角角得得到到2k-1个个选选手手在在后后半半程的比赛日程；程的比赛日程； 算法设计的关键在于寻找这算法设
85、计的关键在于寻找这4部分元素之间的对应关系。部分元素之间的对应关系。nvoidTable(intk,int*a)/2的k次方nnintn=1;nfor(inti=1;i=k;i+)/求得nnn*=2;nfor(inti=1;i=n;i+)/填写第1列na1i=i;nintm=1;nfor(ints=1;s=k;s+)nnn/=2;nfor(intt=1;t=n;t+)nfor(inti=m+1;i=2*m;i+)nfor(intj=m+1;j=2*m;j+)nnaij+(t-1)*m*2=ai-mj+(t-1)*m*2-m;naij+(t-1)*m*2-m=ai-mj+(t-1)*m*2;nnm*=2;nn小结n问题分解是求解复杂问题时很自然的做法，所以，分治法作为一种算法设计策略是非常有价值的。本章通过对二分检索、分治乘法、合并排序等典型实例的讨论，以及分析算法时间复杂度的方法。通过对这些典型范例的学习，有助于加深对分治法乃至递归的深刻内涵的理解，以及对其应用技巧的掌握。重点是二分检索及其性能分析、二阶矩阵乘法等的基本思想。难点是二分检索等各种算法的性态分析。
