算法设计与分析分治法精选PPT.ppt

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

1、关于算法设计与分析关于算法设计与分析分治法分治法第1页，讲稿共62张，创作于星期二2subproblem 2 of size n/2subproblem 1 of size n/2a solution to subproblem 2a problem of size na solution to subproblem 1a solution tothe original problem分治法的基本思想分治法的基本思想第2页，讲稿共62张，创作于星期二3分治法的基本思想分治法的基本思想将规模为将规模为N的问题分解为的问题分解为k个规模较小的子问题个规模较小的子问题,使这些使这些子问题相互独立可分

2、别求解子问题相互独立可分别求解,再将再将k个子问题的解合并成原问题个子问题的解合并成原问题的解的解.如如子问题子问题的规模仍很大的规模仍很大,则则反复分解反复分解直到问题小到可直接直到问题小到可直接求解为止。求解为止。在分治法中在分治法中,子问题的解法通常与原问题相同子问题的解法通常与原问题相同,自然导致自然导致递归过递归过程程。第3页，讲稿共62张，创作于星期二4一个简单的例子：一个简单的例子：N个数字求和，如何用分治法解决？个数字求和，如何用分治法解决？是不是分治法一定比蛮力法高效呢？是不是分治法一定比蛮力法高效呢？串行计算串行计算并行计算并行计算通过分治法解决大问题的时间等于所有解决小问

3、通过分治法解决大问题的时间等于所有解决小问题的时间？题的时间？T(n)=aT(n/b)+f(n)划分为规模为划分为规模为n/b的小问题的小问题a个小问题个小问题解决大问题的消解决大问题的消耗的时间耗的时间合并小问题消耗合并小问题消耗的时间的时间第4页，讲稿共62张，创作于星期二5T(n)=aT(n/b)+f(n)递推式的解法递推式的解法直接使用公式直接使用公式写出分治法解决写出分治法解决n个数字相加问题的效率类型，设每次个数字相加问题的效率类型，设每次分为分为2个子问题个子问题第5页，讲稿共62张，创作于星期二6本章解决的问题：本章解决的问题：排序排序查找查找大整数乘法大整数乘法矩阵乘法矩阵乘

4、法最近对最近对凸包凸包二叉树遍历二叉树遍历第6页，讲稿共62张，创作于星期二74.1 合并排序合并排序 问题：问题：将将n个元素排成非递减顺序。个元素排成非递减顺序。思考如何使用分治法将大问题分成小问题？思考如何使用分治法将大问题分成小问题？第7页，讲稿共62张，创作于星期二8思想思想83297154123456788329238914577154832938291745832971547154分分合合第8页，讲稿共62张，创作于星期二9算法思路：算法思路：若若n为为1,算法终止算法终止;否则否则,将将n个待排元素分割成个待排元素分割成k(k=2)个大致相等子集合个大致相等子集合A、B,对每一

5、个子集合对每一个子集合分别递归排序分别递归排序,再将排好序的子集归并为一个集再将排好序的子集归并为一个集合。合。第9页，讲稿共62张，创作于星期二10合并排序的递归算法合并排序的递归算法算法算法MergeSort(A0.n-1)/输入：未排序序列输入：未排序序列A0.n-1/输出：已排序序列输出：已排序序列A0.n-1ifn1copyA0.n/2-1toB0.n/2-1copyA n/2.n-1toC0.n/2-1MergeSort(B)MergeSort(C)Merge(B,C,A)当前当前n规模规模的问题，分的问题，分成成2个子问题个子问题以同样的方式解决子问题以同样的方式解决子问题用归并

6、排序，形成最终的有序用归并排序，形成最终的有序数组数组第10页，讲稿共62张，创作于星期二11Merge(B,C,A)是将是将有序数组有序数组B、C合并为合并为有序数有序数组组A的算法。的算法。称为归并排序称为归并排序归并排序示例：归并排序示例：1 3 4 9 13 34 672 5 61234569 13 34 67B数组数组C数组数组第11页，讲稿共62张，创作于星期二12前提前提：数组数组B及数组及数组C已经有序已经有序。比较数组比较数组B的第一个记录与数组的第一个记录与数组C的第一个记录的第一个记录将将KEY值小者输出至数组值小者输出至数组A，再从相应数组读进，再从相应数组读进一个记录

7、，替代已被输出的记录，再继续比较。一个记录，替代已被输出的记录，再继续比较。结束结束：直至有一个数组的记录已被穷尽，然后再直至有一个数组的记录已被穷尽，然后再将未穷尽的数组上的所有记录拷贝到输出数组将未穷尽的数组上的所有记录拷贝到输出数组A上。上。第12页，讲稿共62张，创作于星期二13Merge(B0.p-1,C0.q-1,A0.p+q-1)i=0,j=0,k=0;whileipandj1copyA0.n/2-1toB0.n/2-1copyA n/2.n-1toC0.n/2-1MergeSort(B)MergeSort(C)Merge(B,C,A)基本操作？基本操作？似乎较难判断。似乎较难判

8、断。写出总体工作量表达式。写出总体工作量表达式。设设n=2k,总工作量表示为：总工作量表示为：C(n)=(1次除法次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)C(1)=0第14页，讲稿共62张，创作于星期二15简写为简写为C(n)=2C(n/2)+Cmerge(n)+kn基本操作基本操作比较？拷贝？比较？拷贝？(比较的次数不会大于拷贝的次数比较的次数不会大于拷贝的次数)是否和其他因素相关？是否和其他因素相关？最坏情况如何？最坏情况如何？归并排序的效率归并排序的效率Cmerge(n)=n,C(n)=2C(n/2)+sn解得解得C(n)=nlog2n-n+1(nlog2n)

9、C(n)=(1次除法次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)第15页，讲稿共62张，创作于星期二16合并排序结论合并排序结论最坏情况最坏情况(nlog2n)优点：优点：合并排序在最坏情况下的键值比较次数合并排序在最坏情况下的键值比较次数十分接近于十分接近于任任何基于比较的排序算法在何基于比较的排序算法在理论理论上能够达到的最少次数上能够达到的最少次数合并排序精确解合并排序精确解Cworst(n)=nlog2n-n+1理论最小值理论最小值nlog2n-1.44n向上取整向上取整缺点：缺点：需要线性的额外空间，体现在何处？需要线性的额外空间，体现在何处？虽然合并也可做到

10、虽然合并也可做到“在位在位”，但导致算法过于复杂。，但导致算法过于复杂。第16页，讲稿共62张，创作于星期二174.2 快速排序快速排序算法思路算法思路:对于输入对于输入A0.n-1，按以下三个步骤进行排序：，按以下三个步骤进行排序：(1)分区分区:取取A中的一个元素为中的一个元素为支点支点(pivot)将将A0.n-1划分划分成成3段段:A0.s-1,As,As+1.n-1,使得使得A0.s-1中任一元素中任一元素 As,As+1.n-1中任一元素中任一元素 As;下标下标s在划分过程中在划分过程中确定。确定。(2)递归求解递归求解:递归调用快速排序法分别对递归调用快速排序法分别对A0.s-

11、1和和As+1.n-1排序。排序。(3)合并合并:合并合并A0.s-1,As,As+1.n-1为为A0.n-1第17页，讲稿共62张，创作于星期二18493865971327一趟排序后一趟排序后27381349769765分别快排分别快排132738657697第18页，讲稿共62张，创作于星期二19快速排序算法快速排序算法QuickSort(Al.r)/使用快速排序法对序列或者子序列排序使用快速排序法对序列或者子序列排序/输入：子序列输入：子序列Al.r或者序列本身或者序列本身A0.n-1/输出：非递减序列输出：非递减序列AiflrsPartition(Al.r)QuickSort(Al.s

12、-1)QuickSort(As+1.r)/s是中轴元素是中轴元素/基准点，是数组分区位置的标志基准点，是数组分区位置的标志中轴元素如何选？中轴元素如何选？选好中轴后如何扫描数组形成分区？选好中轴后如何扫描数组形成分区？找到分裂点找到分裂点s，分区，分区按同样的方法处理子区间按同样的方法处理子区间第19页，讲稿共62张，创作于星期二20分区的例子（双向扫描）分区的例子（双向扫描）初始数组初始数组A0.n-1=5,3,1,9,8,2,4,7,取元素取元素A0=5作为分裂点作为分裂点,红色表示红色表示i上的元素上的元素，蓝色表示蓝色表示j上的元素上的元素位置位置i0123456753198247i，

13、j上的元素和分裂点比较并移动上的元素和分裂点比较并移动对于对于i遇到比分裂点大或等于时停止遇到比分裂点大或等于时停止对于对于j遇到比分裂点小或等于时停止遇到比分裂点小或等于时停止53198247停止后，停止后，ij交换分裂点和交换分裂点和Aji=jAi=Aj=分裂点上的值分裂点上的值53148297交换后，交换后，i加加1，j减减153148297继续前面的比较和移动继续前面的比较和移动5314289753142897ij交换分裂点和交换分裂点和Aj23145897一次分区完成一次分区完成第20页，讲稿共62张，创作于星期二21数组的分区算法：数组的分区算法：算法算法Partition(Al.

14、r)/输入：子数组输入：子数组Al.r/输出：分裂点输出：分裂点/基准点基准点pivot的位置的位置pAlil;jr+1repeatrepeatii+1untilAiprepeatjj1untilAjpswap(Ai,Aj)untilijswap(Ai,Aj)swap(Al,Aj)returnj第21页，讲稿共62张，创作于星期二22快速排序效率分析快速排序效率分析iflrsPartition(Al.r)QuickSort(Al.s-1)QuickSort(As+1.r)基本操作？基本操作？似乎较难判断。似乎较难判断。写出总体工作量表达式。写出总体工作量表达式。C(n)=Cpartition(

15、n)+CQuickSort(s前面前面)+CQuickSort(s后面后面)第22页，讲稿共62张，创作于星期二23C(n)=Cpartition(n)+CQuickSort(s前面前面)+CQuickSort(s后面后面)上式依赖于上式依赖于s的位置。的位置。考虑考虑partition的的基本操作：基本操作：比较比较一次分区算法的比较次数是否和其他因素相关一次分区算法的比较次数是否和其他因素相关对于对于一次长度为一次长度为n的数组的的数组的分区算法分区算法，如果出现指针交叉，如果出现指针交叉，所执行的比较是所执行的比较是n+1次，为什么？次，为什么？相等，比较次数为相等，比较次数为n次次第2

16、3页，讲稿共62张，创作于星期二24整个算法的最坏情况下：整个算法的最坏情况下：在进行了在进行了n+1次比较后建立了分区，还会对数次比较后建立了分区，还会对数组进行排序，继续到最后一个子数组组进行排序，继续到最后一个子数组An-2.n-1。总比较次数为：总比较次数为：Cworst(n)=(n+1)+n+3=(n+2)(n+1)/2-3(n2)第24页，讲稿共62张，创作于星期二25最好情况最好情况每次分区执行每次分区执行n次次并且每次都是等分并且每次都是等分Cbest(n)=2Cbest(n/2)+n(nlog2n)第25页，讲稿共62张，创作于星期二26平均情况平均情况分裂点有可能在一次分区

17、后出现在每个位置分裂点有可能在一次分区后出现在每个位置设概率是设概率是1/n第26页，讲稿共62张，创作于星期二274.1-4.2 结论结论合并排序最差合并排序最差(nlog2n)快速排序最优快速排序最优(nlog2n)最差最差(n2)平均平均(1.38nlog2n)选择排序选择排序(n2)冒泡排序冒泡排序(n2)第27页，讲稿共62张，创作于星期二284.3 折半查找折半查找(有序数组有序数组)位置：位置：0123456789101112值：值：3,14,27,31,39,42,55,70,74,81,85,93,98K=70迭代迭代1l=0m=6r=12迭代迭代2lm=9r迭代迭代3lr结

18、果结果m=(7+8)/2=7第28页，讲稿共62张，创作于星期二29 BinarySearch(A0.n-1,k)/输入：已排序大小为输入：已排序大小为n的序列的序列A，待搜索对象，待搜索对象k/输出：如果搜索成功，则返回输出：如果搜索成功，则返回k的位置，否则返回的位置，否则返回-1l=0,r=n-1;Whilelr mid=(l+r)/2 ifk=Amidreturnmid elseifkAmidr=m-1elsel=m+1return-1折半查找伪代码折半查找伪代码第29页，讲稿共62张，创作于星期二30折半查找效率分析：基本操作：比较基本操作：比较最坏情况下，比较次数最坏情况下，比较次

19、数C(n)=C(n/2)+1C(1)=1设设n=2k，可解得，可解得C(n)=k+1=log2n+1于是于是C(n)(log2n)第30页，讲稿共62张，创作于星期二314.3 结论结论折半查找折半查找最差最差(log2n)顺序查找顺序查找(n)是一种退化了的分治法是一种退化了的分治法第31页，讲稿共62张，创作于星期二324.4 二叉树遍历及其相关特性二叉树遍历及其相关特性所谓二叉树的遍历指的是遵循某一种次序来访问二叉树上的所谓二叉树的遍历指的是遵循某一种次序来访问二叉树上的所有结点，使得树中每一个结点被访问了一次且只访问一次。所有结点，使得树中每一个结点被访问了一次且只访问一次。由于二叉树

20、是一种非线性结构，树中的结点可能有不止一个由于二叉树是一种非线性结构，树中的结点可能有不止一个的直接后继结点，所以遍历以前必须先规定访问的次序。的直接后继结点，所以遍历以前必须先规定访问的次序。第32页，讲稿共62张，创作于星期二33中序遍历（中序遍历（Inorder Traversal）二叉树的中序遍历算法比较简单，使用递归的策略。在遍二叉树的中序遍历算法比较简单，使用递归的策略。在遍历以前首先确定遍历的树是否为空，如果为空，则直接返历以前首先确定遍历的树是否为空，如果为空，则直接返回；否则中序遍历的算法步骤如下：回；否则中序遍历的算法步骤如下：（1）对左子树）对左子树L执行中序遍历算法执行

21、中序遍历算法（2）访问输出根结点）访问输出根结点V的值。的值。（3）对右子树）对右子树R执行中序遍历算法。执行中序遍历算法。第33页，讲稿共62张，创作于星期二34前序遍历（前序遍历（Preorder Traversal）有了上面的中序遍历的过程，前序遍历也是类似的。在遍有了上面的中序遍历的过程，前序遍历也是类似的。在遍历以前首先确定遍历的树是否为空，如果为空，则直接返历以前首先确定遍历的树是否为空，如果为空，则直接返回；否则前序遍历的算法步骤如下：回；否则前序遍历的算法步骤如下：（1）访问输出根结点）访问输出根结点V的值；的值；（2）对左子树）对左子树L执行前序遍历算法。执行前序遍历算法。（

22、3）对右子树）对右子树R执行前序遍历算法。执行前序遍历算法。第34页，讲稿共62张，创作于星期二35前序遍历执行过程图前序遍历执行过程图第35页，讲稿共62张，创作于星期二36二叉树的构造二叉树的构造第36页，讲稿共62张，创作于星期二37二叉树的高度计算二叉树的高度计算算法算法Height(T)/输入一棵二叉树输入一棵二叉树T/输出二叉树的高度输出二叉树的高度/二叉树高度定义：叶子到树根的最长路径二叉树高度定义：叶子到树根的最长路径ifT=return-1elsereturnmaxHeight(L),Height(R)+1例：计算上例中二叉树的高度例：计算上例中二叉树的高度H(T)=1+ma

23、xH(2),H(6)=2+maxH(3),H(4)=3+H(5)=5第37页，讲稿共62张，创作于星期二384.5 大整数乘法和大整数乘法和Strassen矩阵乘法矩阵乘法整数乘法问题整数乘法问题:设设A和和B为两个为两个N位的整数，计算位的整数，计算它们的乘积它们的乘积AB。思考按照通常做法要执行思考按照通常做法要执行一位一位乘法多少次？乘法多少次？如：234 125 1170 468 234 *N2次。次。第38页，讲稿共62张，创作于星期二39分治法如何体现。分治法如何体现。令令N为偶数，则为偶数，则A和和B可表示为可表示为其中其中a1和和a2分别为分别为A的前半部和后半部。的前半部和后

24、半部。Aa110N/2+a2(123456=123106/2+456)Bbl10N/2+b2bl和和b2则分别为则分别为B的前半部和后半部。如果的前半部和后半部。如果按下述方法得到积按下述方法得到积(多项式相乘多项式相乘)AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2第39页，讲稿共62张，创作于星期二40AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2估算时间效率是多少估算时间效率是多少(即需要多少次一位乘法即需要多少次一位乘法)？则要则要4次次N/2位乘法，

25、即位乘法，即N2次一位乘法。因此这种次一位乘法。因此这种方法没有改进原来的方法。方法没有改进原来的方法。第40页，讲稿共62张，创作于星期二41改进的乘法改进的乘法AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2=a1b110n+(a1+a2)(b1+b2)-a1b1-a2b2)10n/2+a2b2此时需要乘法多少次？此时需要乘法多少次？这种方法需要这种方法需要3次次n/2位位的乘法及的乘法及一些加减法一些加减法。记记C(n)为计算两个为计算两个n位整数相乘所需的基本操位整数相乘所需的基本操作执行次数，则作执行次数，则第41页，

26、讲稿共62张，创作于星期二42有有C(n)=3C(n/2)+knC(1)=1其中，其中，k为常数为常数，KN表示加法、减法所需时间与表示加法、减法所需时间与N成正比。成正比。解此递归方程，得解此递归方程，得C(n)=nlog3+2knlog3-2kn O(nlog3)O(n1.58)可见，乘法效率有改善。可见，乘法效率有改善。第42页，讲稿共62张，创作于星期二43评价评价其原理在于乘法操作所需时间比加法多得多，因其原理在于乘法操作所需时间比加法多得多，因此减少乘法次数，此减少乘法次数，虽然代价为增加加法运算，总的效果还是加速了虽然代价为增加加法运算，总的效果还是加速了运算运算.大整数大整数(

27、500比特或比特或1024比特比特)的乘法用于加密和的乘法用于加密和认证认证.第43页，讲稿共62张，创作于星期二442、Strassen矩阵乘法矩阵乘法矩阵乘法是线性代数中最常见的运算之一，它在数值计矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。算中有广泛的应用。若若A和和B是是2个个nn的矩阵，则它们的乘积的矩阵，则它们的乘积C=AB同样是同样是一个一个nn的矩阵。的矩阵。A和和B的乘积矩阵的乘积矩阵C中的元素中的元素Ci,j定义定义为为:若依此定义来计算若依此定义来计算A和和B的乘积矩阵的乘积矩阵C，则每计算，则每计算C的一的一个元素个元素Ci,j，加法和乘法的次数是

28、多少？，加法和乘法的次数是多少？需要做需要做n个乘法和个乘法和n-1次加法。次加法。因此，求出矩阵因此，求出矩阵C的的n2个元素所需的计算时间为个元素所需的计算时间为O(n3)。第44页，讲稿共62张，创作于星期二45Strassen矩阵乘法矩阵乘法如何对矩阵乘法采用分治？如何对矩阵乘法采用分治？首先，假设首先，假设n=2k。将矩阵将矩阵A，B和和C中每一矩阵都分块成为中每一矩阵都分块成为4个大小个大小相等相等的子矩阵，每个子矩阵都是的子矩阵，每个子矩阵都是n/2n/2的方阵。的方阵。由此可将方程由此可将方程C=AB重写为重写为:第45页，讲稿共62张，创作于星期二46Strassen矩阵乘法

29、矩阵乘法其中：其中：C11C12C21C22是多少？是多少？C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22 第46页，讲稿共62张，创作于星期二47 C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22依此算法，计算依此算法，计算2个个n阶方阵的乘积转化阶方阵的乘积转化为计算为计算8个个n/2阶方阵的乘积阶方阵的乘积和和4个个n/2阶方阵的加法阶方阵的加法上述分治法的计算时间耗费上述分治法的计算时间耗费T(n)如何写？如何

30、写？T(n)=8T(n/2)+cn2T(1)=1计算计算T(n)是多少？是多少？这个递归方程的解仍然属于这个递归方程的解仍然属于O(n3)第47页，讲稿共62张，创作于星期二48Strassen方法方法M1=A11(B12-B22)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)他的算法只用了他的算法只用了7次乘法运算，但增加了加、减法的运算次乘法运算，但增加了加、减法的运算次数次数10次。次。观察使用了多少次观察使用了多少次乘

31、法乘法?加减法用了多少次？加减法用了多少次？第48页，讲稿共62张，创作于星期二49于是可得到于是可得到:C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7引入引入8次加减法次加减法Strassen矩阵乘积分治算法中，用了矩阵乘积分治算法中，用了7次对于次对于n/2阶矩阵乘积的递阶矩阵乘积的递归调用和归调用和18次次n/2阶矩阵的加减运算。阶矩阵的加减运算。由此可知，该算法的所需的计算时间由此可知，该算法的所需的计算时间T(n)满足如下的递归方程满足如下的递归方程:第49页，讲稿共62张，创作于星期二50Strassen矩阵乘法矩阵乘法其解为其解为

32、T(n)O(nlog7)O(n2.81)。由此可见，由此可见，Strassen矩阵乘法的计算时间复杂性比矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。普通矩阵乘法有阶的改进。T(n)=7T(n/2)+kn2T(1)=1第50页，讲稿共62张，创作于星期二51结论结论大整数乘法和矩阵乘法分别利用了将乘法转换为大整数乘法和矩阵乘法分别利用了将乘法转换为多个加法进行替代。多个加法进行替代。对于矩阵乘法可以将矩阵作对于矩阵乘法可以将矩阵作33的划分，即将矩的划分，即将矩阵分成九个子矩阵，或作阵分成九个子矩阵，或作44的划分的划分(即将矩阵即将矩阵分成十六个子矩阵分成十六个子矩阵)。相应地要求矩阵的

33、阶相应地要求矩阵的阶n是是3的整次幂的整次幂(或或4的整次幂的整次幂)。有人沿这个途径改善了矩阵乘法的复杂度。有人沿这个途径改善了矩阵乘法的复杂度。第51页，讲稿共62张，创作于星期二524.6 分治法解最近点对问题和凸包问题分治法解最近点对问题和凸包问题问题问题:给定平面给定平面S上上n个点个点,找其中的一对点找其中的一对点,使得在使得在n(n-1)/2个个点对中点对中,该点对的距离最小。该点对的距离最小。算法思路算法思路:1)n较小时直接求较小时直接求(n=2).2)将将S上的上的n个点分成大致相等的个点分成大致相等的2个子集个子集S1和和S2 3)分别求分别求S1和和S2中的最接近点对中

34、的最接近点对 4)求一点在求一点在S1、另一点在、另一点在S2中的最近点对中的最近点对 5)从上述三对点中找距离最近的一对从上述三对点中找距离最近的一对.第52页，讲稿共62张，创作于星期二532)将将S上的上的n个点分成大致相等的个点分成大致相等的2个子集个子集S1和和S2如何分？如何分？将点按照将点按照x轴升序排序轴升序排序画一条垂直线画一条垂直线x=c第53页，讲稿共62张，创作于星期二543)递归求递归求S1和和S2中的最接近点对中的最接近点对d1，d2d=mind1,d2是否这就是最小距离？是否这就是最小距离？不一定，距离最近的点可能位于分界线的两侧不一定，距离最近的点可能位于分界线

35、的两侧第54页，讲稿共62张，创作于星期二554)求一点在求一点在S1、另一点在、另一点在S2中的最近点对中的最近点对是否需要考察是否需要考察S1和和S2中的所有的点？中的所有的点？只需考察以只需考察以x=c为对称的宽度为为对称的宽度为2d的垂直带中的垂直带中为什么？为什么？令令C1和和C2是垂直带左右部分点构成的子集。是垂直带左右部分点构成的子集。对于对于C1中的每一个点中的每一个点P(x,y)检查检查C2中的每一个点中的每一个点和和P之间的距离是否小于之间的距离是否小于d是否需要考察是否需要考察C2中所有的点？中所有的点？该过程是线性的该过程是线性的第55页，讲稿共62张，创作于星期二56

36、递推式递推式T(n)=2T(n/2)+M(n)得到得到T(n)属于属于O(nlogn)第56页，讲稿共62张，创作于星期二57凸包问题凸包问题凸集定义：凸集定义：设设S是平面点集，如果是平面点集，如果S中任意两点的连线都中任意两点的连线都属于该集合，则称属于该集合，则称S是凸的是凸的p84。凸包定义：凸包定义：一个点集一个点集S的凸包是指包含的凸包是指包含S的最小凸集。的最小凸集。显然，如果显然，如果S是凸的，则是凸的，则S的凸包就是的凸包就是S本身本身（橡皮筋圈解释）。（橡皮筋圈解释）。凸包问题：凸包问题：给定一个给定一个n个点的点集个点的点集S，求，求S的凸包。的凸包。第57页，讲稿共62

37、张，创作于星期二58基本思想：基本思想：1将点按将点按x轴升序排列轴升序排列2找出最左点找出最左点P1和最右点和最右点Pn，一定是该集合的凸，一定是该集合的凸包顶点包顶点3P1到到Pn的直线将凸包分成上下包的直线将凸包分成上下包4采用同样的方法构造上下包采用同样的方法构造上下包A在在S1中找距离中找距离P1Pn的最远点的最远点Pmax，如何找？，如何找？BPmax是顶点是顶点CP1PmaxPn形成形成4个区域，顶点可能出现在何处？个区域，顶点可能出现在何处？D用同样的方法处理相应区域用同样的方法处理相应区域第58页，讲稿共62张，创作于星期二59效率分析：效率分析：最差情况最差情况第59页，讲稿共62张，创作于星期二60总结总结第60页，讲稿共62张，创作于星期二61作业作业赛程问题赛程问题:有有N个运动员进行单循环赛，即每个个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。运动员要和所有其他运动员进行一次比赛。试用分治法为这试用分治法为这N个运动员安排比赛日程。个运动员安排比赛日程。要求每个运动员每天只进行一场比赛，要求每个运动员每天只进行一场比赛，且整个赛程在且整个赛程在N-1天内结束。天内结束。将运动员从将运动员从1到到N编号。编号。第61页，讲稿共62张，创作于星期二感谢大家观看第62页，讲稿共62张，创作于星期二