《算法设计与分析分治法讲稿.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析分治法讲稿.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于算法设计与分关于算法设计与分析分治法析分治法第一页，讲稿共六十二页哦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分治法的基本思想分治法的基本思想第二页，讲稿共六十二页哦3分治法的基本思想分治法的基本思想将规模为将规模为N的问题分解为的问题分解为k个规模较小的子问题个规模较小的子问题,使这些子使这些子问题相互独立可分别求解问题相互独立
2、可分别求解,再将再将k个子问题的解合并成原问题个子问题的解合并成原问题的解的解.如如子问题子问题的规模仍很大的规模仍很大,则则反复分解反复分解直到问题小到可直接直到问题小到可直接求解为止。求解为止。在分治法中在分治法中,子问题的解法通常与原问题相同子问题的解法通常与原问题相同,自然导致自然导致递归递归过程过程。第三页，讲稿共六十二页哦4一个简单的例子：一个简单的例子：N个数字求和，如何用分治法解决？个数字求和，如何用分治法解决？是不是分治法一定比蛮力法高效呢？是不是分治法一定比蛮力法高效呢？串行计算串行计算并行计算并行计算通过分治法解决大问题的时间等于所有解决小问通过分治法解决大问题的时间等于
3、所有解决小问题的时间？题的时间？T(n)=aT(n/b)+f(n)划分为规模为划分为规模为n/b的小问题的小问题a个小问题个小问题解决大问题的解决大问题的消耗的时间消耗的时间合并小问题消合并小问题消耗的时间耗的时间第四页，讲稿共六十二页哦5T(n)=aT(n/b)+f(n)递推式的解法递推式的解法直接使用公式直接使用公式写出分治法解决写出分治法解决n个数字相加问题的效率类型，设每次个数字相加问题的效率类型，设每次分为分为2个子问题个子问题第五页，讲稿共六十二页哦6本章解决的问题：本章解决的问题：排序排序查找查找大整数乘法大整数乘法矩阵乘法矩阵乘法最近对最近对凸包凸包二叉树遍历二叉树遍历第六页，
4、讲稿共六十二页哦74.1 合并排序合并排序 问题：问题：将将n个元素排成非递减顺序。个元素排成非递减顺序。思考如何使用分治法将大问题分成小问题？思考如何使用分治法将大问题分成小问题？第七页，讲稿共六十二页哦8思想思想83297154123456788329238914577154832938291745832971547154分分合合第八页，讲稿共六十二页哦9算法思路：算法思路：若若n为为1,算法终止算法终止;否则否则,将将n个待排元素分割成个待排元素分割成k(k=2)个大致相等子集合个大致相等子集合A、B,对每一个子集合对每一个子集合分别递归排序分别递归排序,再将排好序的子集归并为一个集再将
5、排好序的子集归并为一个集合。合。第九页，讲稿共六十二页哦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个子问题个子问题以同样的方式解决子问题以同样的方式解决子问题用归并排序，形成最终的有用归并排序，形成最终的有序数组序数组第十页，讲稿共六十二页哦11Merg
6、e(B,C,A)是将是将有序数组有序数组B、C合并为合并为有序数有序数组组A的算法。的算法。称为归并排序称为归并排序归并排序示例：归并排序示例：1 3 4 9 13 34 672 5 6123 45 69 13 34 67B数组数组C数组数组第十一页，讲稿共六十二页哦12前提前提：数组数组B及数组及数组C已经有序已经有序。比较数组比较数组B的第一个记录与数组的第一个记录与数组C的第一个记录的第一个记录将将KEY值小者输出至数组值小者输出至数组A，再从相应数组读进，再从相应数组读进一个记录，替代已被输出的记录，再继续比较。一个记录，替代已被输出的记录，再继续比较。结束结束：直至有一个数组的记录已
7、被穷尽，然后再直至有一个数组的记录已被穷尽，然后再将未穷尽的数组上的所有记录拷贝到输出数组将未穷尽的数组上的所有记录拷贝到输出数组A上。上。第十二页，讲稿共六十二页哦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)基本操作？基本操作？似乎较难判断。似乎较难判断。写出总体工作量表达式。写出总体工作量表达式。设设n=2k,总工作量表示为：总工作量表示为：C(n)=(1次除法次除
8、法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)C(1)=0第十四页，讲稿共六十二页哦15简写为简写为C(n)=2C(n/2)+Cmerge(n)+kn基本操作基本操作比较？拷贝？比较？拷贝？(比较的次数不会大于拷贝的次数比较的次数不会大于拷贝的次数)是否和其他因素相关？是否和其他因素相关？最坏情况如何？最坏情况如何？归并排序的效率归并排序的效率Cmerge(n)=n,C(n)=2C(n/2)+sn解得解得C(n)=nlog2n-n+1(nlog2n)C(n)=(1次除法次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)第十五页，讲稿共六十二页哦16合并排序结
9、论合并排序结论最坏情况最坏情况(nlog2n)优点：优点：合并排序在最坏情况下的键值比较次数合并排序在最坏情况下的键值比较次数十分接近于十分接近于任任何基于比较的排序算法在何基于比较的排序算法在理论理论上能够达到的最少次数上能够达到的最少次数合并排序精确解合并排序精确解Cworst(n)=nlog2n-n+1理论最小值理论最小值nlog2n-1.44n向上取整向上取整缺点：缺点：需要线性的额外空间，体现在何处？需要线性的额外空间，体现在何处？虽然合并也可做到虽然合并也可做到“在位在位”，但导致算法过于复杂。，但导致算法过于复杂。第十六页，讲稿共六十二页哦174.2 快速排序快速排序算法思路算法
10、思路:对于输入对于输入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-1和和As+1.n-1排序。排序。(3)合并合并:合并合并A0.s-1,As,As+1.n-1为为A0.n-1第十七页，讲稿共六十二页哦184938
11、65971327一趟排序后一趟排序后27381349769765分别快排分别快排132738657697第十八页，讲稿共六十二页哦19快速排序算法快速排序算法QuickSort(Al.r)/使用快速排序法对序列或者子序列排序使用快速排序法对序列或者子序列排序/输入：子序列输入：子序列Al.r或者序列本身或者序列本身A0.n-1/输出：非递减序列输出：非递减序列AiflrsPartition(Al.r)QuickSort(Al.s-1)QuickSort(As+1.r)/s是中轴元素是中轴元素/基准点，是数组分区位置的标志基准点，是数组分区位置的标志中轴元素如何选？中轴元素如何选？选好中轴后如何
12、扫描数组形成分区？选好中轴后如何扫描数组形成分区？找到分裂点找到分裂点s，分区，分区按同样的方法处理子区间按同样的方法处理子区间第十九页，讲稿共六十二页哦20分区的例子（双向扫描）分区的例子（双向扫描）初始数组初始数组A0.n-1=5,3,1,9,8,2,4,7,取元素取元素A0=5作为分裂点作为分裂点,红色表示红色表示i上的元素上的元素，蓝色表示蓝色表示j上的元素上的元素位置位置i0123456753198247i，j上的元素和分裂点比较并移动上的元素和分裂点比较并移动对于对于i遇到比分裂点大或等于时停止遇到比分裂点大或等于时停止对于对于j遇到比分裂点小或等于时停止遇到比分裂点小或等于时停止
13、53198247停止后，停止后，ij交换分裂点和交换分裂点和Aji=jAi=Aj=分裂点上的值分裂点上的值53148297交换后，交换后，i加加1，j减减153148297继续前面的比较和移动继续前面的比较和移动5314289753142897ij交换分裂点和交换分裂点和Aj23145897一次分区完成一次分区完成第二十页，讲稿共六十二页哦21数组的分区算法：数组的分区算法：算法算法Partition(Al.r)/输入：子数组输入：子数组Al.r/输出：分裂点输出：分裂点/基准点基准点pivot的位置的位置pAlil;jr+1repeatrepeatii+1untilAiprepeatjj1u
14、ntilAjpswap(Ai,Aj)untilijswap(Ai,Aj)swap(Al,Aj)returnj第二十一页，讲稿共六十二页哦22快速排序效率分析快速排序效率分析iflrsPartition(Al.r)QuickSort(Al.s-1)QuickSort(As+1.r)基本操作？基本操作？似乎较难判断。似乎较难判断。写出总体工作量表达式。写出总体工作量表达式。C(n)=Cpartition(n)+CQuickSort(s前面前面)+CQuickSort(s后面后面)第二十二页，讲稿共六十二页哦23C(n)=Cpartition(n)+CQuickSort(s前面前面)+CQuickS
15、ort(s后面后面)上式依赖于上式依赖于s的位置。的位置。考虑考虑partition的的基本操作：基本操作：比较比较一次分区算法的比较次数是否和其他因素相关一次分区算法的比较次数是否和其他因素相关对于对于一次长度为一次长度为n的数组的的数组的分区算法分区算法，如果出现指针交叉，如果出现指针交叉，所执行的比较是所执行的比较是n+1次，为什么？次，为什么？相等，比较次数为相等，比较次数为n次次第二十三页，讲稿共六十二页哦24整个算法的最坏情况下：整个算法的最坏情况下：在进行了在进行了n+1次比较后建立了分区，还会对数次比较后建立了分区，还会对数组进行排序，继续到最后一个子数组组进行排序，继续到最后
16、一个子数组An-2.n-1。总比较次数为：总比较次数为：Cworst(n)=(n+1)+n+3=(n+2)(n+1)/2-3(n2)第二十四页，讲稿共六十二页哦25最好情况最好情况每次分区执行每次分区执行n次次并且每次都是等分并且每次都是等分Cbest(n)=2Cbest(n/2)+n(nlog2n)第二十五页，讲稿共六十二页哦26平均情况平均情况分裂点有可能在一次分区后出现在每个位置分裂点有可能在一次分区后出现在每个位置设概率是设概率是1/n第二十六页，讲稿共六十二页哦274.1-4.2 结论结论合并排序最差合并排序最差(nlog2n)快速排序最优快速排序最优(nlog2n)最差最差(n2)
17、平均平均(1.38nlog2n)选择排序选择排序(n2)冒泡排序冒泡排序(n2)第二十七页，讲稿共六十二页哦284.3 折半查找折半查找(有序数组有序数组)位置：位置：0123456789101112值：值：3,14,27,31,39,42,55,70,74,81,85,93,98K=70迭代迭代1l=0m=6r=12迭代迭代2lm=9r迭代迭代3lr结果结果m=(7+8)/2=7第二十八页，讲稿共六十二页哦29 BinarySearch(A0.n-1,k)/输入：已排序大小为输入：已排序大小为n的序列的序列A，待搜索对象，待搜索对象k/输出：如果搜索成功，则返回输出：如果搜索成功，则返回k的
18、位置，否则返回的位置，否则返回-1l=0,r=n-1;Whilelr mid=(l+r)/2 ifk=Amidreturnmid elseifkAmidr=m-1elsel=m+1return-1折半查找伪代码折半查找伪代码第二十九页，讲稿共六十二页哦30折半查找效率分析：基本操作：比较基本操作：比较最坏情况下，比较次数最坏情况下，比较次数C(n)=C(n/2)+1C(1)=1设设n=2k，可解得，可解得C(n)=k+1=log2n+1于是于是C(n)(log2n)第三十页，讲稿共六十二页哦314.3 结论结论折半查找折半查找最差最差(log2n)顺序查找顺序查找(n)是一种退化了的分治法是一
19、种退化了的分治法第三十一页，讲稿共六十二页哦324.4 二叉树遍历及其相关特性二叉树遍历及其相关特性所谓二叉树的遍历指的是遵循某一种次序来访问二叉树上所谓二叉树的遍历指的是遵循某一种次序来访问二叉树上的所有结点，使得树中每一个结点被访问了一次且只访问一次。的所有结点，使得树中每一个结点被访问了一次且只访问一次。由于二叉树是一种非线性结构，树中的结点可能有不止由于二叉树是一种非线性结构，树中的结点可能有不止一个的直接后继结点，所以遍历以前必须先规定访问的次一个的直接后继结点，所以遍历以前必须先规定访问的次序。序。第三十二页，讲稿共六十二页哦33中序遍历（中序遍历（Inorder Traversa
20、l）二叉树的中序遍历算法比较简单，使用递归的策略。在遍历以二叉树的中序遍历算法比较简单，使用递归的策略。在遍历以前首先确定遍历的树是否为空，如果为空，则直接返回；否则前首先确定遍历的树是否为空，如果为空，则直接返回；否则中序遍历的算法步骤如下：中序遍历的算法步骤如下：（1）对左子树）对左子树L执行中序遍历算法执行中序遍历算法（2）访问输出根结点）访问输出根结点V的值。的值。（3）对右子树）对右子树R执行中序遍历算法。执行中序遍历算法。第三十三页，讲稿共六十二页哦34前序遍历（前序遍历（Preorder Traversal）有了上面的中序遍历的过程，前序遍历也是类似的。在遍历以有了上面的中序遍历
21、的过程，前序遍历也是类似的。在遍历以前首先确定遍历的树是否为空，如果为空，则直接返回；否则前首先确定遍历的树是否为空，如果为空，则直接返回；否则前序遍历的算法步骤如下：前序遍历的算法步骤如下：（1）访问输出根结点）访问输出根结点V的值；的值；（2）对左子树）对左子树L执行前序遍历算法。执行前序遍历算法。（3）对右子树）对右子树R执行前序遍历算法。执行前序遍历算法。第三十四页，讲稿共六十二页哦35前序遍历执行过程图前序遍历执行过程图第三十五页，讲稿共六十二页哦36二叉树的构造二叉树的构造第三十六页，讲稿共六十二页哦37二叉树的高度计算二叉树的高度计算算法算法Height(T)/输入一棵二叉树输入
22、一棵二叉树T/输出二叉树的高度输出二叉树的高度/二叉树高度定义：叶子到树根的最长路径二叉树高度定义：叶子到树根的最长路径ifT=return-1elsereturnmaxHeight(L),Height(R)+1例：计算上例中二叉树的高度例：计算上例中二叉树的高度H(T)=1+maxH(2),H(6)=2+maxH(3),H(4)=3+H(5)=5第三十七页，讲稿共六十二页哦384.5 大整数乘法和大整数乘法和Strassen矩阵乘法矩阵乘法整数乘法问题整数乘法问题:设设A和和B为两个为两个N位的整数，计算位的整数，计算它们的乘积它们的乘积AB。思考按照通常做法要执行思考按照通常做法要执行一位
23、一位乘法多少次？乘法多少次？如：234 125 1170 468 234 *N2次。次。第三十八页，讲稿共六十二页哦39分治法如何体现。分治法如何体现。令令N为偶数，则为偶数，则A和和B可表示为可表示为其中其中a1和和a2分别为分别为A的前半部和后半部。的前半部和后半部。Aa110N/2+a2(123456=123106/2+456)Bbl10N/2+b2bl和和b2则分别为则分别为B的前半部和后半部。如果的前半部和后半部。如果按下述方法得到积按下述方法得到积(多项式相乘多项式相乘)AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b
24、2第三十九页，讲稿共六十二页哦40AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2估算时间效率是多少估算时间效率是多少(即需要多少次一位乘法即需要多少次一位乘法)？则要则要4次次N/2位乘法，即位乘法，即N2次一位乘法。因此这种次一位乘法。因此这种方法没有改进原来的方法。方法没有改进原来的方法。第四十页，讲稿共六十二页哦41改进的乘法改进的乘法AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2=a1b110n+(a1+a2)(b1+b2)-a1b1-a2b2)10n
25、/2+a2b2此时需要乘法多少次？此时需要乘法多少次？这种方法需要这种方法需要3次次n/2位位的乘法及的乘法及一些加减法一些加减法。记记C(n)为计算两个为计算两个n位整数相乘所需的基本操位整数相乘所需的基本操作执行次数，则作执行次数，则第四十一页，讲稿共六十二页哦42有有C(n)=3C(n/2)+knC(1)=1其中，其中，k为常数为常数，KN表示加法、减法所需时间与表示加法、减法所需时间与N成正比。成正比。解此递归方程，得解此递归方程，得C(n)=nlog3+2knlog3-2kn O(nlog3)O(n1.58)可见，乘法效率有改善。可见，乘法效率有改善。第四十二页，讲稿共六十二页哦43
26、评价评价其原理在于乘法操作所需时间比加法多得多，因其原理在于乘法操作所需时间比加法多得多，因此减少乘法次数，此减少乘法次数，虽然代价为增加加法运算，总的效果还是加速了虽然代价为增加加法运算，总的效果还是加速了运算运算.大整数大整数(500比特或比特或1024比特比特)的乘法用于加密和的乘法用于加密和认证认证.第四十三页，讲稿共六十二页哦442、Strassen矩阵乘法矩阵乘法矩阵乘法是线性代数中最常见的运算之一，它在数值计矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。算中有广泛的应用。若若A和和B是是2个个nn的矩阵，则它们的乘积的矩阵，则它们的乘积C=AB同样是同样是一个
27、一个nn的矩阵。的矩阵。A和和B的乘积矩阵的乘积矩阵C中的元素中的元素Ci,j定义定义为为:若依此定义来计算若依此定义来计算A和和B的乘积矩阵的乘积矩阵C，则每计算，则每计算C的一个的一个元素元素Ci,j，加法和乘法的次数是多少？，加法和乘法的次数是多少？需要做需要做n个乘法和个乘法和n-1次加法。次加法。因此，求出矩阵因此，求出矩阵C的的n2个元素所需的计算时间为个元素所需的计算时间为O(n3)。第四十四页，讲稿共六十二页哦45Strassen矩阵乘法矩阵乘法如何对矩阵乘法采用分治？如何对矩阵乘法采用分治？首先，假设首先，假设n=2k。将矩阵将矩阵A，B和和C中每一矩阵都分块成为中每一矩阵都
28、分块成为4个大小个大小相等相等的子矩阵，每个子矩阵都是的子矩阵，每个子矩阵都是n/2n/2的方阵。的方阵。由此可将方程由此可将方程C=AB重写为重写为:第四十五页，讲稿共六十二页哦46Strassen矩阵乘法矩阵乘法其中：其中：C11C12C21C22是多少？是多少？C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22 第四十六页，讲稿共六十二页哦47 C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22依此算法，计算依此算法，
29、计算2个个n阶方阵的乘积转化阶方阵的乘积转化为计算为计算8个个n/2阶方阵的乘积阶方阵的乘积和和4个个n/2阶方阵的加法阶方阵的加法上述分治法的计算时间耗费上述分治法的计算时间耗费T(n)如何写？如何写？T(n)=8T(n/2)+cn2T(1)=1计算计算T(n)是多少？是多少？这个递归方程的解仍然属于这个递归方程的解仍然属于O(n3)第四十七页，讲稿共六十二页哦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)M
30、7=(A11-A21)(B11+B12)他的算法只用了他的算法只用了7次乘法运算，但增加了加、减法的运算次乘法运算，但增加了加、减法的运算次数次数10次。次。观察使用了多少次观察使用了多少次乘法乘法?加减法用了多少次加减法用了多少次？第四十八页，讲稿共六十二页哦49于是可得到于是可得到:C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7引入引入8次加减法次加减法Strassen矩阵乘积分治算法中，用了矩阵乘积分治算法中，用了7次对于次对于n/2阶矩阵乘积的递阶矩阵乘积的递归调用和归调用和18次次n/2阶矩阵的加减运算。阶矩阵的加减运算。由此可知，该
31、算法的所需的计算时间由此可知，该算法的所需的计算时间T(n)满足如下的递归方程满足如下的递归方程:第四十九页，讲稿共六十二页哦50Strassen矩阵乘法矩阵乘法其解为其解为T(n)O(nlog7)O(n2.81)。由此可见，由此可见，Strassen矩阵乘法的计算时间复杂性比矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。普通矩阵乘法有阶的改进。T(n)=7T(n/2)+kn2T(1)=1第五十页，讲稿共六十二页哦51结论结论大整数乘法和矩阵乘法分别利用了将乘法转换为大整数乘法和矩阵乘法分别利用了将乘法转换为多个加法进行替代。多个加法进行替代。对于矩阵乘法可以将矩阵作对于矩阵乘法可以将矩阵
32、作33的划分，即将矩的划分，即将矩阵分成九个子矩阵，或作阵分成九个子矩阵，或作44的划分的划分(即将矩阵即将矩阵分成十六个子矩阵分成十六个子矩阵)。相应地要求矩阵的阶相应地要求矩阵的阶n是是3的整次幂的整次幂(或或4的整次幂的整次幂)。有人沿这个途径改善了矩阵乘法的复杂度。有人沿这个途径改善了矩阵乘法的复杂度。第五十一页，讲稿共六十二页哦524.6 分治法解最近点对问题和凸包问题分治法解最近点对问题和凸包问题问题问题:给定平面给定平面S上上n个点个点,找其中的一对点找其中的一对点,使得在使得在n(n-1)/2个点对中个点对中,该点对的距离最小。该点对的距离最小。算法思路算法思路:1)n较小时直
33、接求较小时直接求(n=2).2)将将S上的上的n个点分成大致相等的个点分成大致相等的2个子集个子集S1和和S2 3)分别求分别求S1和和S2中的最接近点对中的最接近点对 4)求一点在求一点在S1、另一点在、另一点在S2中的最近点对中的最近点对 5)从上述三对点中找距离最近的一对从上述三对点中找距离最近的一对.第五十二页，讲稿共六十二页哦532)将将S上的上的n个点分成大致相等的个点分成大致相等的2个子集个子集S1和和S2如何分？如何分？将点按照将点按照x轴升序排序轴升序排序画一条垂直线画一条垂直线x=c第五十三页，讲稿共六十二页哦543)递归求递归求S1和和S2中的最接近点对中的最接近点对d1
34、，d2d=mind1,d2是否这就是最小距离？是否这就是最小距离？不一定，距离最近的点可能位于分界线的两侧不一定，距离最近的点可能位于分界线的两侧第五十四页，讲稿共六十二页哦554)求一点在求一点在S1、另一点在、另一点在S2中的最近点对中的最近点对是否需要考察是否需要考察S1和和S2中的所有的点？中的所有的点？只需考察以只需考察以x=c为对称的宽度为为对称的宽度为2d的垂直带中的垂直带中为什么？为什么？令令C1和和C2是垂直带左右部分点构成的子集。是垂直带左右部分点构成的子集。对于对于C1中的每一个点中的每一个点P(x,y)检查检查C2中的每一个点中的每一个点和和P之间的距离是否小于之间的距
35、离是否小于d是否需要考察是否需要考察C2中所有的点？中所有的点？该过程是线性的该过程是线性的第五十五页，讲稿共六十二页哦56递推式递推式T(n)=2T(n/2)+M(n)得到得到T(n)属于属于O(nlogn)第五十六页，讲稿共六十二页哦57凸包问题凸包问题凸集定义：凸集定义：设设S是平面点集，如果是平面点集，如果S中任意两点的连线都中任意两点的连线都属于该集合，则称属于该集合，则称S是凸的是凸的p84。凸包定义：凸包定义：一个点集一个点集S的凸包是指包含的凸包是指包含S的最小凸集。的最小凸集。显然，如果显然，如果S是凸的，则是凸的，则S的凸包就是的凸包就是S本身本身（橡皮筋圈解释）。（橡皮筋
36、圈解释）。凸包问题：凸包问题：给定一个给定一个n个点的点集个点的点集S，求，求S的凸包。的凸包。第五十七页，讲稿共六十二页哦58基本思想：基本思想：1将点按将点按x轴升序排列轴升序排列2找出最左点找出最左点P1和最右点和最右点Pn，一定是该集合的凸，一定是该集合的凸包顶点包顶点3P1到到Pn的直线将凸包分成上下包的直线将凸包分成上下包4采用同样的方法构造上下包采用同样的方法构造上下包A在在S1中找距离中找距离P1Pn的最远点的最远点Pmax，如何找？，如何找？BPmax是顶点是顶点CP1PmaxPn形成形成4个区域，顶点可能出现在何处？个区域，顶点可能出现在何处？D用同样的方法处理相应区域用同
37、样的方法处理相应区域第五十八页，讲稿共六十二页哦59效率分析：效率分析：最差情况最差情况第五十九页，讲稿共六十二页哦60总结总结第六十页，讲稿共六十二页哦61作业作业赛程问题赛程问题:有有N个运动员进行单循环赛，即每个个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。运动员要和所有其他运动员进行一次比赛。试用分治法为这试用分治法为这N个运动员安排比赛日程。个运动员安排比赛日程。要求每个运动员每天只进行一场比赛，要求每个运动员每天只进行一场比赛，且整个赛程在且整个赛程在N-1天内结束。天内结束。将运动员从将运动员从1到到N编号。编号。第六十一页，讲稿共六十二页哦感谢大家观看第六十二页，讲稿共六十二页哦