【教学课件】第2章递归与分治.ppt

2005,第2章 递归与分治策略,最通用的算法设计技术学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过典型的范例学习分治策略设计技巧。,2,2.1 递归的概念,例1:阶乘函数 阶乘函数可递归地定义为：,注意：(1)边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。(2)非递归定义：,3,2.1 递归的概念,例2:Fibonacci数列问题引入裴波那契（Fibonacci leonardo，约1170-1250）是意大利著名数学家在他的著作算盘书中许多有趣的问题，最富成功的问题是著名的“兔子繁殖问题”：如果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？问题分析,4,2.1 递归的概念,数列的特点（1）数列的增长速度（2）自然科学中的若干实例（3）构造一个新数列,5,定义：,2.1 递归的概念,6,2.1 递归的概念,如何求解？解法1：0(0.618n)int fibonacci(int n)if(n=0)|(n=1)return n;return fibonacci(n-1)+fibonacci(n-2);解法2：0(n)解法3：0(logn),7,2.1 递归的概念,思考：楼梯问题有一楼梯共有n阶，上楼可以一步上一阶，也可以一步上两阶。编一个程序，计算共有多少种不同的走法？,8,例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n,m)定义如下：,2.1 递归的概念,9,2.1 递归的概念,Ackerman函数A(n,0)n+2A(n,1)2nA(n,2)2n。A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,10,2.1 递归的概念,例4 排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。集合X中元素的全排列记为perm(X)，(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。,11,2.1 递归的概念,R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n1时，perm(R)由:(r1)perm(R1)(r2)perm(R2)(rn)perm(Rn)构成。参考算法：,12,2.1 递归的概念,例5 整数划分问题将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个划分。形如：nn1n2nk其中：(ni1，i1,2,k，k1)且 nn1n2nk 1,13,2.1 递归的概念,例如：整数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;,14,2.1 递归的概念,分析：将最大加数n1不大于m的划分个数记作q(n,m)(1)q(n,1)=1,n1;(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1 n-1的划分组成。(4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1 m-1 的划分组成。,15,而：正整数n的划分数p(n)=q(n,n)。,2.1 递归的概念,因此：q(n,m)的递归定义如下,16,2.1 递归的概念,例6 Hanoi塔问题问题描述：,17,问题分析：,2.1 递归的概念,Hanoi(n,A,B,C),圆盘数 源柱 辅助柱 目标柱,18,=,+,+,2.1 递归的概念,19,递归求解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);递归函数的运行轨迹,2.1 递归的概念,20,Hanio(3,A,B,C),Hanio(2,A,C,B),Hanio(1,A,B,C),Move(A,C),Move(A,B),Hanio(1,C,A,B),Move(C,B),Move(A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move(B,C),Hanio(1,A,B,C),Move(A,C),Move(B,A),21,分析：规模为n的Hanoi(n)问题，可以分解为2个规模为n-1的Hanoi(n-1)问题和一个Move 操作。所以，n个盘子的移动次数为,2.1 递归的概念,若n=64，则移动次数为264-1,264118,446,744,073,709,551,615,22,264118,446,744,073,709,551,615是个什么概念？实例1：假设每秒钟移动一次，一年约31556926秒，计算表明：移动64个盘子需要5800多亿年。实例2：国王的麦子问题,23,广义hanoi问题问题描述算法分析,Hanoi(n,A,B,C,D),圆盘数 源柱 辅助柱 目标柱,2.1 递归的概念,24,2.1 递归的概念,递归的优点和缺点优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,25,2.1 递归的概念,26,2.1 递归的概念,消除递归的方法采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。用递推来实现递归函数。通过变换能将一些递归转化为尾递归，从而迭代求出结果。注意：后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,27,分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。-孙子兵法,2.2 分治法的基本思想,28,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，且各个子问题是相互独立的，即子问题之间不包含公共的子问题。利用该问题分解出的子问题的解可以合并为该问题的解；,29,2.2 分治法的基本思想,分治法（Divide and Conquer）的基本思想:分解(Divide)：将一个规模为n的问题，分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同。求解(Conquer):若子问题规模较小而容易被解决则直接解，否则递归地解这些子问题。合并(Merge)：将各个子问题的解合并得到原问题的解。,30,2.2 分治法的基本思想,分治法的 设计模式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);/将各子问题的解合并/为原问题的解,31,2.2 分治法的基本思想,启发式规则：平衡子问题：在用分治法设计算法时，最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。,32,2.2 分治法的基本思想,分治法的典型情况,33,分治法的时间复杂性分析,通过迭代法求得方程的解：,2.2 分治法的基本思想,34,例：二分搜索技术,问题提出：给定已按升序排好序的n个元素a0:n1，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的各个子问题是相互独立的。分解出的子问题的解可以合并为原问题的解；,35,例1:二分搜索技术,36,补充材料减治法,减治法的基本思想减治法（reduce and conquer method）将原问题分解为若干个子问题后，只求解其中一个子问题：原问题的解只存在于其中一个较小规模的子问题中原问题的解与其中一个较小规模的子问题的解之间存在对应关系；减治法是一种退化了的分治法。,37,补充材料减治法,减治法的典型情况：,38,分治法的应用,数值计算问题中的分治法组合问题中的分治法排序问题中的分治法几何问题中的分治法,39,应用专题一,数值计算问题中的分治法大整数的乘法strassen矩阵乘法,40,引：大整数的存储与运算计算机存储数据是按类型分配空间的。例如：在微型机上，为整型提供2个字节的存储空间，则整型数据的范围为3276832767；为长整型提供4个字节的存储空间，则长整型数据的范围为21474836482147483647；,大整数的乘法,41,大整数的乘法,为实型提供4个字节的存储空间，但不是精确存储数据，只有6位精度，数据的范围(3.4e-383.4e+38)；为双精度型数据提供8个字节的存储空间，数据的范围(1.7e-3081.7e+308)，其精确位数是17位。,42,在用数组存储高精度数据时，从计算的方便性考虑，决定将数据是由低到高还是由高到低存储到数组中；可以每位占一个数组元素空间，也可几位占一个数组元素空间。若需从键盘输入要处理的高精度数据，一般用字符数型组存储，这样无需对高精度数据进行分段输入。,大整数的乘法,43,当N=100时，N！的准确值问题分析：问题要求对输入的正整数N，计算N！的准确值，而N！的增长速度仅次于指数增长的速度，所以这是一个高精度计算问题。,大整数的乘法,44,大整数的乘法,例如：9！=362880100！=93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916864000000 000000 000000 000000,45,问题描述：设X和Y都是n位的二进制整数，请设计一个有效的算法，可以进行两个n位大整数的乘法运算。分析：1.小学的方法：O(n2)效率太低,46,2.可以用分治法的原理设计一个更有效的算法。将n位的二进制整数分为2段：,则：X=A2n/2+B（乘2n/2，相当于左移n/2位）Y=C2n/2+D于是：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD(1),47,大整数的乘法,效率：4次n/2位整数乘法(AC,AD,BC,BD)；3次不超过n位整数加法；2次移位(分别对应乘以2n和2n/2)所有加法和移位共用O(n)步计算。,时间复杂性分析T(n)=O(n2)没有改进,48,时间复杂性分析 T(n)=O(nlog3)=O(n1.59)较大的改进,大整数的乘法,改进：把(1)式稍作修改：XY=AC2n+(AB)(DC)+AC+BD)2n/2+BD(2)效率：3次n/2位整数乘法(AC,BD,(AB)(DC)；6次不超过n位整数加、减法和2次移位；,49,大整数的乘法,Char*Mult(char X,char Y,int n)/两个n位整数相乘 S=sign(X)*sign(Y);/取乘积的符号 X=abs(X);Y=abs(Y);if(n=1)return(S*X*Y);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;,注意：该算法可改为十进制数乘法，只需将基数2变为10，即：2n 10n,2n/2 10n/2,50,大整数的乘法,小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进,51,大整数的乘法,更快的方法？如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生，该方法也可以看作是一个复杂的分治算法。对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。,52,strassen矩阵乘法,传统的方法若A和B是2个nn的矩阵，则它们的乘积C=AB同样是一个nn的矩阵。A和B的乘积矩阵C中的元素Ci,j定义为:,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Ci,j，需要做n个乘法和n1次加法。因此，求出矩阵C的n2个元素所需的计算时间为O(n3)。,53,分治法将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵，每个子矩阵都是n/2n/2的方阵。由此可将方程C=AB重写为：,由此可得：,strassen矩阵乘法,54,为了降低时间复杂度，必须减少乘法的次数。Strassen矩阵乘法,strassen矩阵乘法,55,验证: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,strassen矩阵乘法,56,strassen矩阵乘法,57,完整的Strassen算法如下：STRASSEN(n,A,B,C)if(n=2)MATRIX-MULTIPLY(A，B，C);/普通2*2矩阵相乘 else/将矩阵A和B分块;STRASSEN(n/2,A11,B12-B22,M1);STRASSEN(n/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);,strassen矩阵乘法,58,strassen矩阵乘法,传统方法：O(n3)分治法:O(n2.81)Strassen将2个n/2阶方阵乘积的乘法次数由传统的8次变为7次，但增加了加、减法的运算次数。Strassen矩阵乘法目前没有太大实际意义。当n 120时，它与普通矩阵乘法在计算时间上并无明显的差异。只有当n很大时，才会显示出优越性。,59,strassen矩阵乘法,更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个22矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了，或许应当研究33或55矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)。是否能找到O(n2)的算法？,60,应用专题二,组合问题中的分治法棋盘覆盖问题循环日程赛安排问题最大子段和问题,61,问题描述：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,棋盘覆盖问题,62,棋盘覆盖问题,例如：k2时的一个特殊棋盘,2k2k 的棋盘覆盖中，用到的骨牌数为(4k-1)/3,63,例如：,棋盘覆盖问题,64,分析：当k=0时，有1种覆盖方案当k 0时，考虑采用分治策略：,棋盘覆盖问题,65,算法实现：P18,棋盘覆盖问题,66,算法分析:设T(k)为覆盖2k2k残缺棋盘的时间,当k=0时覆盖它需要常数时间O(1);当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k1)。,T(k)=O(4k)渐进意义下的最优算法,棋盘覆盖问题,67,还可以将棋盘覆盖推广到一般情况：,棋盘覆盖问题,68,问题描述：设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n1天。,循环赛日程表,69,循环赛日程表,例如：,70,循环赛日程表,分析：法1：分治策略按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,71,循环赛日程表,分析法2：递推法(迭代法),72,循环赛日程表,递推法(迭代法)即2k个选手的比赛日程在2k-1个选手的比赛日程基础上通过迭代完成，每次迭代，将问题分为4个部分：左上角：2k-1个选手前半程的比赛日程左下角：另2k-1个选手前半程的比赛日程，由左上角加2k-1得到右上角：将左下角抄到右上角，得到另2k-1个选手后半程的比赛日程。右上角：将左上角抄到右下角，得到2k-1个选手后半程的比赛日程。,73,问题提出：给定由n个整数（可能为负数）组成的序列：a1,a2,an,求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。依其定义，所求的最优值为：,最大子段和问题,74,1.最大子段和问题的简单算法int MaxSum(int n,int*a,int 显然：T(n)=O(n3),最大子段和问题,75,2.一点改进int MaxSum(int n,int an,int 显然：T(n)=O(n2),最大子段和问题,76,3.最大子段和问题的分治策略划分：按照平衡子问题的原则，将序列(a1,a2,an)划分成长度相同的两个子序列(a1,an/2)和(an/21,an)；求解子问题：合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的大者为原问题的解。,最大子段和问题,77,最大子段和问题,78,Int MaxSubSum(int an,int left,int right)int sum=0;if(left=right)sum=aleft0?aleft:0;else int center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right);int s1=0,lefts=0;for(int j=center;j=left;j-)lefts+=aj;if(lefts s1)s1=lefts;int s2=0,rights=0;for(int j=center+1;j s2)s2=rights;,最大子段和问题,79,sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;/elsereturn sum;Int MaxSum(int n,int a)return MaxSubSum(a,1,n);,复杂度分析,最大子段和问题,80,最大子段和问题,应用举例：最佳游览路线问题问题描述：某旅游区的街道成网格状。其中：东西向的街道为旅游街，南北向的为林荫道。规定旅游街为单行道，旅客只能从西向东走；在林荫道即可从南向北，也可从北向南。,81,阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。,82,应用专题三,排序问题中的分治法合并排序快速排序选择问题,83,合并排序,基本思想：划分：将待排序元素分成大小大致相同的2个子序列求解子问题分别对2个子序列进行排序合并将排好序的两个子序列合并成为一个有序序列。,84,合并排序,二路归并排序的分治策略是：划分：将待排序序列r1,r2,rn划分为两个长度相等的子序列r1,rn/2和rn/21,rn；求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；合并：将这两个有序子序列合并成一个有序序列。,85,合并排序,如图所示,86,合并排序,算法描述（递归）：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)渐进意义下的最优算法,87,消去递归,合并排序,88,快速排序,快速排序的分治策略：划分选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 ri-1和ri+1 rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；求解子问题分别对划分后的每一个子序列递归处理；合并由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。,89,快速排序,r1 ri-1 ri ri+1 rn 均ri 轴值 均ri 位于最终位置,90,一次划分,38,91,templateint Partition(Type a,int p,int r)int i=p,j=r;Type x=ap;while(ix)j-;ai=aj;while(ij,一次划分算法,92,快速排序,以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。,13,27,50,38,49,55,j,i,i,j,13,65,27,50,38,49,55,65,93,快速排序算法,void QuickSort(Type a,int p,int r)if(pr)int q=Partion(a,p,r)QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序,94,快速排序时间复杂性分析,快速排序算法的性能取决于划分的对称性。,最坏情况复杂度分析,最好情况复杂度分析,平均情况复杂度分析,问题：轴值的选取？（1）传统的方法（2）一种安全的做法-随机选取（3）中值法三值中值法,95,基本思想：在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。,随机选择策略的快速排序,96,随机选择策略的快速排序,随机数发生器int random(int a,int b)return rand()%(ba)+a随机化的划分算法int randomizedPartion(type a,int p,int r)int i=ramdom(p,r);swap(ai,ap);return Partition(a,p,r);,97,随机选择策略的快速排序,void QuickSort_random(Type a,int p,int r)if(pr)int q=randomizedpartion(a,p,r)QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序,int i=ramdom(p,r);swap(ai,ap);int q=Partition(a,p,r);,98,2006计算机科学学院 刘芳 60,各排序算法平均时间的曲线图,99,选择问题,问题提出：设无序序列T=r1,r2,rn，T的第k（1kn）小的元素定义为T按升序排列后在第k个位置上的元素。对给定序列T和一个整数k，寻找T的第k小的元素的问题称为选择问题。应用：选择问题的一个应用就是寻找中值元素。,100,选择问题,应用实例中值滤波在信号采集过程中，由于电子设备的不稳定性会对获取的信号产生噪声，中值滤波就是一种降噪技术。一维信号中值滤波是用中值代替规定位置（一般是原始信号序列的中心位置）的信号值。对二维的数字图像而言，中值滤波就是用一个活动窗口沿图像移动，窗口中心位置的象素灰度用窗口内所有象素灰度的中值来代替。,101,解决方法法1：排序法 O(nlogn)法2：基于划分的选择算法平均情况：T(n)O(n)法3：线性时间选择 最坏情况：T(n)O(n),选择问题,102,法2：基于划分的选择算法：Template Type randomizedSelect(int p,int r,int k)if(p=r)return ap;int i=randomizedpartition(p,r),j=ip+1;if(k=j)return ai;else if(kj)return randomizedSelect(p,i,k);else return randomizedSelect(i+1,r,kj);,选择问题,103,分析：,最好情况复杂度分析（若分点总是等分点）,最坏情况复杂度分析(分点左半总为空),平均情况复杂度分析,104,法3：线性时间选择：,选择问题,105,算法的时间复杂度分析,选择问题,106,应用专题四,几何问题中的分治法最接近点对问题凸包问题,107,问题描述：设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。,最接近点对问题,108,最接近点对问题,简单应用假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。,109,最接近点对问题,分析：直接方法：通过检查所有的n(n1)/2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为(n2)。分治法,110,最接近点对问题,算法描述：if(n=2)用直接法寻找最近点对;else 将点集分成大致相等的两个部分A和B 确定A中最近的点对；确定B中的最近点对；确定一点在A中、另一点在B中的最近点对；从上面得到的三对点中，找出距离最小的一对点；,111,最接近点对问题,一维的情形,112,最接近点对问题,分析：按这种分治策略求解最近对问题的算法效率取决于划分点m的选取，一个基本的要求是要遵循平衡子问题的原则。如果选取m(maxS+minS)/2，则有可能因集合S中点分布的不均匀而造成子集S1和S2的不平衡，如果用S中各点坐标的中位数（即S的中值）作为分割点，则会得到一个平衡的分割点m，使得子集S1和S2中有个数大致相同的点。,113,最接近点对问题,下面来考虑二维的情形,114,最接近点对问题,应用分治法求解含有n个点的最近点对问题，其时间复杂性可由下面的递推式表示：,115,凸包问题,凸包：平面上的一个点集的凸包是包含所有点的最小凸多边形，或说是围绕所有点的最短路径。凸包应用：求凸包问题是一个基本集合计算。它在许多统计计算，特别是高维统计计算中起着重要的作用。许多计算几何的问题都是从求凸包开始，所以它是计算几何的基础问题。,116,凸包问题,分治算法求解凸包问题设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，并且这些点按照x轴坐标升序排列。几何学中有这样一个明显的事实：最左边的点p1和最右边的点pn一定是该集合的凸包顶点（即极点）。凸包上包下包,117,如图：,118,凸包问题,快包的思想,119,集合S1的上包首先找到S1中的顶点pmax，它是距离直线p1pn最远的顶点，则三角形pmaxp1pn的面积最大。S1中所有在直线pmaxp1左侧的点构成集合S1,1S1中所有在直线pmaxpn右侧的点构成集合S1,2包含在三角形pmaxp1pn之中的点可以不考虑了。递归地继续构造集合S1,1的上包和集合S1,2的上包，将求解过程中得到的所有最远距离的点连接起来，就可以得到集合S1的上包。,120,凸包问题,问题:如何判断一个点是否在给定直线的左侧（或右侧）？分析：几何学中有这样一个定理：如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三个点，则三角形p1p2p3的面积等于下面这个行列式的绝对值的一半：,121,凸包问题,并且有结论:当且仅当点p3=(x3,y3)位于直线p1p2的左侧时，该式的符号为正。于是：可以在一个常数时间内检查一个点是否位于两个点确定的直线的左侧，并且可以求得这个点到该直线的距离。,122,本章小结,知识点理解递归的概念。掌握设计有效算法的分治策略及时间复杂性递归方程的求解；掌握分治法的典型范例的求解思想，并加以应用数值计算问题排序问题几何问题组合问题,