1、Algorithms Design Techniques and Analysis第六章 分 治Algorithms Design Techniques and Analysis本章主要内容本章主要内容分治基本概念引言 两个简单例子二分搜索合并排序分治范式分治策略解决的一些问题选择算法快速排序大整数乘法矩阵乘法最近点问题Algorithms Design Techniques and Analysis6.1 引言什么是分治算法形式?一个分治算法把问题实例划分成若干子实例(多数情况是分成两个)；并分别递归地解决每个子实例；然后把这些子实例的解组合起来，得到原问题实例的解；Algorithms D
2、esign Techniques and Analysis寻找最大值和最小值 问题描述 在一个整数组A1.n中，同时寻找最大值和最小值。为了简化问题，不妨假定n是2的整数幂。一种直接的算法如下1.xA1;yA12.for i2 to n3.if Aiy then yAi5.end for6.return(x,y)显然，由此方法显然，由此方法执行的元素比较执行的元素比较次数是次数是2n一一2是否存在更有效的算法是否存在更有效的算法?Algorithms Design Techniques and Analysis分治方法 基本思想 将数组分割成两半，A1.n/2 和A(n/2)+1.n；在每一半
3、中找到最大值和最小值；并返回这两个最小值中的最小值及这两个最大值中的最大值；Algorithms Design Techniques and Analysis算法算法6.1 MINMAX输入输入:n个整数元素的数组A1.n，n为2的幂。输出输出:(x,y):A中的最大元素和最小元素。1.minmax(1,n)过程 minmax(low,high)1.if high-low=1 then 数组只有2个值的情况 2.if AlowAhigh then return(Alow,Ahigh)3.else return(Ahigh,Alow)4.end if 5.else 6.mid(low+high)
4、/2 7.(x1,y1)minmax(low,mid)8.(x2,y2)minmax(mid+1,high)9.xmin(x1,x2)10.ymax(y1,y2)11.return(x,y)12.end if Algorithms Design Techniques and Analysis算法分析 设C(n)表示算法在由n个元素(n是2的整数幂)组成的数组上执行的元素比较次数。见P112 定理 6.1 设数组A1.n包含n个元素，其中n是2的幂，则仅用3n/2一2次元素比较就能够在数组A中找出最大和最小元素。2 if 2)2/(22 if 1)(nnCnnCAlgorithms Design
5、 Techniques and Analysis6.2 二分搜索 问题描述 在数组A1.n中搜索已知元素x 基本思想将一个给定的元素x与一个已排序数组Alow.high.的中间元素做比较 如果x Amid，则放弃Alow.mid，而对Amid+1.high重复实施相同的方法.Algorithms Design Techniques and Analysis算法算法6.2 BINARYSEARCHREC输入:按非降序排列的n个元素的数组A1.n和元素x。输出:如果x=Aj，1j n，则输出j；否则输出0 1.binarysearch(1,n)过程 binarysearch(low,high)1.
6、if lowhigh then return 0 2.else 3.mid(low+high)/2 4.if x=Amid then return mid 5.else if xAmid then return binarysearch(low,mid-1)6.else return binarysearch(mid+1,high)7.end ifAlgorithms Design Techniques and Analysis算法分析 假设 为了求出算法的执行时间，我们计算元素间的比较次数，因为这是一个基本运算，也就是说，算法的执行时间与完成元素间比较次数是成比例的(见1.11.2节)。我们
7、将假定每个三向比较当做一次比较来计算推导见P113 定理6.2算法BINARYSEARCHREC在n个元素组成的数组中搜索某个元素所执行的元素比较次数不超过logn+1。算法BINARYSEARCHREC的时间复杂性是O(logn)。算法递归深度为O(log n)，并且由于每个递归层次需要(l)的空间，本算法所需的空间总量是(log n)。和递归算法相反，其迭代形式算法仅需要(l)空间Algorithms Design Techniques and Analysis6.3 合并排序 BOTTOMUPSORT:在每一层中，我们有已排序的序列对，同时它们两两被合并而得到较大的排序序列。沿着树一层一
8、层向上继续这个过程，直到到达根为止，这最后的序列是已经排序好的。让我们从反向来考虑，是否能用自顶向下取代自底向上？Algorithms Design Techniques and Analysis合并排序 基本思想 首先，将该数组分成两个各一半元素的数组 接着分别对这两个数组的元素排序 然后只是将它们合并来得到所希望的排序数组 至于对每一半子数组，可随意使用任何排序算法来对这两个子数组排序。特别是可以使用算法SORT本身。如果这样，我们实际上得出了著名的算法MERGESORT，此算法的完整描述见下面。Algorithms Design Techniques and Analysis算法算法6.
9、3 Mergesort输入输入:n个元素的数组A1.n。输出输出:按非降序排列的数组A1.n。1.mergesort(A,1,n)过程 mergesort(A,low,high)1.if lowhigh then2.mid(low+high)/23.mergesort(A,low,mid)4.mergesort(A,mid+1,high)5.MERGE(A,low,mid,high)6.end if Algorithms Design Techniques and Analysis6.3.1 算法的操作过程?算法MERGESORT对下列数组A排序的操作过程：A=9,4,5,2,1,7,4,6.
10、定义 mergesort(A,low,high)为 MS(low,high).Merge(A,low,mid,high)为 M(low,mid,high).Algorithms Design Techniques and AnalysisMERGESORT算法过程9452174612445679945224591746146749942552171746469944552211774466Success!MS(1,8)MS(1,4)MS(1,2)MS(1,1)M(1,1,1)MS(2,2)M(2,2,2)M(1,1,2)MS(3,4)MS(3,3)M(3,3,3)MS(4,4)M(4,4,4)
11、M(3,3,4)M(1,2,4)MS(5,8)MS(5,6)MS(5,5)M(5,5,5)MS(6,6)M(6,6,6)M(5,5,6)MS(7,8)M(7,7,8)M(7,7,7)M(8,8,8)M(5,6,8)MS(7,7)MS(8,8)M(1,4,8)Algorithms Design Techniques and AnalysisHow the algorithm works?这个调用链对应于树的前序遍历:访问根、左子树和右子树。计算却对应于树的后序遍历:访问左子树，右子树，最后是根。为了实现这个遍历，用一个栈来存储每次调用过程的局部数据。在算法BOTPOMUPSORT中，合并是一层接
12、一层进行的;而在算法MERGESORT中，合并是以后序遍历的方式进行的。两种算法的区别仅在于合并的次序，因此，当n是2的幂时，由算法MERGESORT执行的比较次数和算法BOTIOMUPSORT执行的次数相同。Algorithms Design Techniques and Analysis6.3.2 合并算法分析 基本运算:元素比较。为了简单，假定n是2的幂。如果n=1，则算法不执行任何元素的比较，比较次数是0。如果 n2，则将问题分解为(whose size is n)2个子问题(whose size are n/2)。合并两个子数组所需的元素比较次数在n/2与n-1之间。这样算法所需的最
13、小比较次数：1n if 0 2n if 2)2(2 )(nncnc2log)(nnncAlgorithms Design Techniques and Analysis合并算法分析 最大比较次数：1log 12 )12(02 2)1(2 12.22)2(2 .122)2(2 12)2(2 1)12)2(2(2 1)2(2)()(1021222221n if 02n if 1)2(2nnnknknkncknncnncnnncnnncnncncnckkkkjjkkkkknncAlgorithms Design Techniques and Analysis合并算法分析 如果n是任意的正整数(不必是
14、2的幂)，对于由算法MERGESORT执行的元素比较次数：定理6.3 算法MERGESORT对一个n个元素的数组排序所需的时间是(nlogn)，空间是(n)。)log()(2n if bn)2nc()2nc(1n if 0)(nnncnc Algorithms Design Techniques and Analysis6.4 分治范式P117一般来说分治范式由以下的步骤组成 划分步骤。在算法的这个步骤中，输入被分成p 1个部分，每个子实例的规模严格小于n，n是原始实例的规模。尽管比2大的其他小的常数很普遍，但P的最常用的值是2。治理步骤。如果问题的规模大于某个预定的阈值n。，这个步骤由执行P
15、个递归调用组成，阈值是由算法的数学分析导出的 组合步骤。这个步骤是组合P个递归调用的解来得到期望的输出值。Algorithms Design Techniques and Analysis一般而言，分治算法有以下形式如果实例I的规模是“小”的，则使用直接的方法求解问题并返回其答案，否则继续做下一步。把实例I分割成P个大小几乎相同的子实例I1,I2,.,Ip。对每个子实例Ij，1jp,递归调用算法，并得到P个部分解。组合P个部分解的结果得到原实例I的解，返回实例I的解。Algorithms Design Techniques and Analysis6.5 寻找中项和第k小元素 选择问题 在一个
16、包含n个元素的集合中寻找第k个最小元素。(中值是第n/2个最小元素)直接方法:对所有的元素排序并取出中间一个元素，这个方法需要(nlogn)时间，因为任何基于比较的排序过程在最坏的情况下必须至少要花费这么多时间 Can we find an efficient method in optimal linear time?能否在最优线性时间内找到更快的算法？Algorithms Design Techniques and AnalysisSELECT 算法假设递归算法中，在每个递归调用的划分步骤后，我们丢弃元素的一个固定部分并且对剩余的元素递归。则问题的规模以几何级数递减，也就是在每个调用过程中
17、，问题的规模以一个常因子被减小。假设某个算法丢弃1/3并对剩余的2/3部分递归，那么在第二次调用中，元素的数目变为2n/3个，第三次调用中为4n/9，第四次调用中变为8n/27，等等。现在假定在每次调用中，算法对每个元素耗费的时间不超过一个常数，则耗费在处理所有元素上的全部时间产生一个几何级数：这里。c是某个被适当选择的常数，由等式2.12，这个总数小于.)32(.)32()32(2 cncncncnj)(3)32(0ncncnjj Algorithms Design Techniques and AnalysisSELECT 算法基本思想首先，如果元素个数小于预定义的阈值44，则算法使用直接
18、的方法计算第k小的元素，至于如何选择阂值在以后的算法分析中将会清楚。下一步把n个元素划分成n/5组，每组由5个元素组成，如果n不是5的倍数，则排除剩余的元素，这应当不影响算法的执行。每组进行排序并取出它的中项即第三个元素接着将这些中项序列中的中项元素记为mm，它是通过递归计算得到的。将数组A中的元素划分成三个数组:A1,A2,A3，其中分别包含小于、等于和大于mm的元素。最后，求出第k小的元素出现在三个数组中的哪一个，并根据测试结果，算法或者返回第k小的元素，或者在A1 or A3上递归。Algorithms Design Techniques and Analysis算法算法6.4 SELE
19、CT输入输入:n个元素的数组A1.n和整数k,1k n。输出输出:A中的第k小元素。1.select(A,1,n,k)过程过程 select(A,low,high,k)1.phigh-low+12.if p44 then 将A排序 return(Ak)3.Let q=p/5.将A分成9组，每组5个元素。如果5不整除P，则排除剩余的元素4.将q组中的每一组单独排序，找出中项。所有中项的集合为M5.mmselect(M,1,q,q/2)mm 为中项集合的中项6.将Alow.high 分成三组:A1=a|amm7.case|A1|k:return select(A1,1,|A1|,k)|A1|+|A
20、2|k:return mm|A1|+|A2|k:return select(A3,1,|A3|,k-|A1|-|A2|)8.end case Algorithms Design Techniques and Analysis例子 为方便起见，让我们暂时将算法中的阈值44改为一个较小的数6 假设存在数组A1.25:8,33,17,51,57,49,35,11,25,37,14,3,2,13,32,12,6,29,32,54,5,16,22,23,7 我们要在数组A中找到第13个最小的元素Algorithms Design Techniques and Analysis例子8 33 17 51 5
21、7 49 35 11 25 3714 3213 52 12629 32 54516 22 23 7partition8 33 17 51 57 49 35 11 25 37 14 3213 52 12 629 32 54 5 16 2223 7sort8 17 33 51 57 11 25 35 37 49 23 13 14 526 12 29 32 54 5 71622 23median1316 29 33 35partition8 17 11 25 14 3 2 13 12 6 5 16 22 23 72933 51 57 49 35 37 5232 54discardAlgorithms
22、 Design Techniques and Analysis例子8 17 11 25 14 3 2 13 12 6 5 16 22 23 7A115partition8 17 11 25 1432 13 12 65 16 22 23 7sort8 11 14 17 2523612 135 716 22 23median6 14 16partition8 11 32 13 12 6 5 71417 25 16 22 23discardAlgorithms Design Techniques and Analysis例子17 25 16 22 23A1115sort16 17 22 23 25S
23、ucceed!The result is A13=22Algorithms Design Techniques and Analysisselection算法分析其中的元素已被划分成具有5元素的各个组，每组元素从底到顶按升序排列。而且这些组以这样的方式整齐排列:它们的中项是从左到右以升序排列的。Algorithms Design Techniques and Analysisselection算法分析所有围在矩形W 中的元素是小于或等于mm的，所有围在矩形x中的元素是大于或等于mm 的。设A1表示小于或等于mm的元素集，A3是大于或等于mm的元素集这个算法中，A1是严格小于mm的元素集，A3是
24、严格大于mm的元素集Algorithms Design Techniques and Analysis 由于A1至少与w同样大，我们有 因此 由参数的对称性得到 这样就为在A1和A3的元素个数建立了上界：即小于mm的元素的个数和大于mm的元素个数不能够超过大约0.7n(n的常分数倍)。Algorithms Design Techniques and Analysis时间复杂度算法的运行时间T(n)P112 在算法中select过程的步骤1和步骤2耗费的时间都是(1)步骤3为(n)时间。由于对每组排序需要时间为常量，步骤4耗费(n)时间，步骤5所需的时间为T(n/5)，步骤6需要(n)时间。由以
25、上的分析，步骤7耗费的时间至多是T(0.7n+1.2)。当n 44时，如果0.7n+1.2 0.75n-1这个不等式将成立。得出的结论为，对于n 44，步骤7所耗费的时间至多是T(0.75n)。Algorithms Design Techniques and Analysis时间复杂度 这个分析蕴含着算法SELECT的运行时间有以下的递推式 定理6.4 在一个由n个元素组成的线序集合中提取第k小元素，所需的时间是(n)，特别地，n个元素的中值可以在(n)时间找出。20cn 435114443544cnT(n)ncn if)nT()nT(n if c T(n)Algorithms Design
26、Techniques and Analysis6.6 快速排序 快速排序是另外一种排序算法,该排序算法具有(nlogn)的平均运行时间 这个算法优于MERGESORT算法的一点是它在原位上排序，即对于被排序的元素，不需要辅助的存储空间。Algorithms Design Techniques and Analysis6.6.1 划分算法 基本思想 设Alow.high是一个包含n个数的数组，并且x=Alow 我们考虑重新安排数组A中的元素的问题，使得小于或等于x的元素在x的前面，随后x又在所有大于它的元素的前面 经过数组中元素改变排列后，对于某个w，lowwhigh，x在Aw 中。例如,如果A
27、=,3,9,2,7,1,8；则经过重新排列其中的元素后，得到 A=1,3,2,7,9,8 其中 w=4。55Algorithms Design Techniques and Analysis划分算法这种重排列行动也称为围绕x的拆分或划分，x称为主元或拆分元素。定义6.1 如果元素Aj既不小于Alow.j-1中的元素，也不大于Aj+1.high中的元素，则称其处在一个适当位置或正确位置。观察结论6.2 用x(x A)作为主元划分数组A后，x将处于一个正确位置。Algorithms Design Techniques and Analysis算法算法6.5 SPLIT输入:数组Alow.high.
28、输出:(1)如有必要，输出按上述描述的重新排列的数组A。(2)划分元素Alow的新位置w。1.ilow2.xAlow3.for jlow+1 to high4.if Aj x then5.ii+16.if i j then 互换Ai and Aj7.end if 8.end for9.互换Alow and Ai10.wi11.return A and wAlgorithms Design Techniques and Analysis例子6570758085605550ij65x=jjjjijij50Success!Algorithms Design Techniques and Analys
29、is算法分析 观察结论6.3 由算法SPLIT执行的元素比较次数恰好是n-1，这样它的时间复杂性为(n)。最后注意到算法仅仅用到一个额外空间用于存储它的局部变量，因此算法的空间复杂性为(1)。Algorithms Design Techniques and Analysis6.6.2 快速排序算法 基本思想 要排序的元素Alow.high通过算法SPLIT重新排列元素，使得原先在Alow中的主元占据其正确的位置Aw，并且所有小于或等于Aw的元素所处的位置为Alow.w-1，而所有大于Aw的元素所处的位置是Aw+1.high。子数组Alow.w-1和Aw1.high 递归地排序，自动产生整个排序
30、数组Algorithms Design Techniques and Analysis算法6.6 QIUCKSORT输入:n个元素的数组A1.n输出:按非降序排列的数组A中的元素1.quicksort(A,1,n)过程 quicksort(A,low,high)1.if lowhigh then2.SPLIT(Alow.high,w)w为Alow的新位置3.quicksort(A,low,w-1)4.quicksort(A,w+1,high)5.end ifAlgorithms Design Techniques and Analysis例子 假设数组A=4,6,3,1,8,7,2,5.463
31、1872523148765231123113376587685576576766766Success!Algorithms Design Techniques and AnalysisMERGESORT 和 QUICKSORT 算法SPLIT和算法QUICKSORT的关系类似于算法MERGE和算法MERGESORT的关系。两个排序算法都由名为SPLIT和MERGE的算法之一的一系列调用组成。在算法MERGESORT中，合并排序序列属于组合步骤，而在算法QUICKSORT中的划分过程则属于划分步骤。事实上，在算法QUICKSORT中组合步骤是不存在的。Algorithms Design Tech
32、niques and Analysis6.6.3 快速排序算法分析 空间复杂度:虽然算法不需要辅助空间存储数组元素，但算法还是至少需要(n)的空间，工作空间在(logn)和(n)之间变化。这是因为在每次递归调用中，表示下一次要排序的数组右边部分的左右界w1和high必须保存。Algorithms Design Techniques and Analysis6.6.3.1 最坏情况的行为 定理6.5 在最坏的情况下，算法QUICKSORT的运行时间是(n2)，然而如果总是选择中项作为主元，它的时间复杂性是(nlogn)。推导见P116Algorithms Design Techniques an
33、d Analysis6.6.3.2 平均情况的行为 假设 假定对于数1，2，n的i个排列中的每一个排列的出现是等可能性的，这一点确保了在数组中的每个数以同样可能作为第一个元素，并被选为主元，也就是说，数组A中的任意元素被选为主元的概率是1/n.设C(n)表示对大小为n的输入数据算法所做的平均比较次数，根据观察结论6.3，得到：步骤2恰好耗费n-1次比较；步骤3和步骤4分别耗费了C(w-1)和C(n-w)次比较；因此总的比较次数为：11()(1)(1)()nwC nnC wC nwnAlgorithms Design Techniques and Analysis 因为 因此 如果用n-1代替n
34、，得到：推导见P1176.6.3.2 平均情况的行为Algorithms Design Techniques and Analysis 等式6.3减去等式6.4，再重新排列各项得到 现在把变量更换为一个新的变量D，并设 那么,其解为6.6.3.2 平均情况的行为Algorithms Design Techniques and Analysis 因为 结果,定理6.6:算法QUICKSORT对n个元素的数组进行排序执行的平均比较次数是(nlogn)。6.6.3.2平均情况的行为Algorithms Design Techniques and Analysis6.7 大整数乘法 我们假定大小一定的
35、整数相乘需要耗费定量的时间，而当两个任意长的整数相乘时，这个假定就不再有效了 对于处理不定长数的算法的数据输入，通常是按二进制的位数来计算的(或按二进制数字来计算)设u和v是两个n位的整数，传统的乘法算法需要(n2)数字相乘来计算u和v的乘积。Is there much more efficient method?Algorithms Design Techniques and Analysis6.7 大整数乘法 设u和v都是n位的二进制整数，现在要计算它们的乘积u*v。我们可以用小学所学的方法来设计一个计算乘积u*v的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法
36、看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积u*v。下面我们用分治法来设计一个更有效的大整数乘积算法。我们将n位的二进制整数u和v各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，Algorithms Design Techniques and Analysis分治技术xzwzxywyzyxwuvnnnn 2222222/)()(:/xwun 22 1241 if nbn)T(n/if ndnT )(假定n是2的幂.wx:/zyvn 22yzu和v的乘积可以计算为：时间复杂度函数为：递推式的解：)()(2nnT n/2n/2Algorithms Design Tech
37、niques and Analysis分治技术xzwyzyxwxywz)(xzxzwyzyxwwyuvnn22)(21n if )2(31n if )(bnnTdnT)()()(59.13lognnnT现在考虑：我们得到：时间复杂度是：递推式的解是：Algorithms Design Techniques and Analysis6.8 矩阵乘法 两个矩阵 A，B：A 的列数等于 B 的行数，则A、B可以相乘。即，如果 A=（aij）是一个m*n的矩阵，B=（bjk）是一个 n*p 的矩阵，则它们的乘积 C=AB 是 m*p 矩阵 C=（cik）。A23B32C22Algorithms Des
38、ign Techniques and Analysis6.8 矩阵乘法 问题描述 令A和B是两个nn的矩阵，我们希望计算它们的乘积C=AB。Algorithms Design Techniques and Analysis6.8.1 矩阵乘法在传统方法中，C=AB是由以下公式计算的 因为每计算一个元素Ci，j，需要做 n 个乘法和 n 1 次加法很容易看出算法需要n3次乘法运算和n3-n2次加法运算。这导致其时间复杂度为(n3).nkjkBkiAjiC1),(),(),(Is there much more efficient method?Algorithms Design Techniqu
39、es and Analysis6.8.2 递归方法假定n=2k，k 0，如果n2，则A，B和C可分别分成4个大小为n/2n/2的子矩阵用分治方法来计算C的组成：222112112221121122211211 CC CCC,BB BBB,AA AAA22221121212211212212121121121111BAB ABABABAB ABABACAlgorithms Design Techniques and Analysis递归方法计算量总耗费是：最终结果：观察结论 6.4 递归方法需要n3次乘法运算和n3-n2次加法运算，这些刚好和前面传统方法所讲述的一样。两种算法的区别仅仅在于矩阵元
40、素相乘的次序上，其他方面是一样的 224281 )(2a if n)n()nT(if n m nT233222322)282()282()(ananmnnanamnT Algorithms Design Techniques and Analysis6.8.3 STRASSEN算法 基本思想 增加加减法的次数来减少乘法次数22211211 aa aaA22211211 bb bbB222112112221121122211211 bb bb aa aa cc ccC和Algorithms Design Techniques and AnalysisSTRASSEN算法 基本思想我们首先计算以下
41、的乘积接着从一下面式子计算出C)()()()()(3)()(222122127121111216221211511212242212111122212221122111bbaadbbaadbaadbbadbbadbaadbbaad 623142537541 dddd ddd d ddddCAlgorithms Design Techniques and Analysis时间复杂度 算法用到的加法是18次，乘法是7次，对于其运行时间产生以下递推式（P121）2218271 )(2if na )n()nT(if nmnT 229271 )(2f n i)na()nT(if nmnT27log7lo
42、g2227log2266)272)29()272)29()(ananmnnanamnT )()(81.27lognn 或即运行时间为：Algorithms Design Techniques and Analysis时间复杂度 Strassen算法的高效之处，就在于，它成功的减少了乘法次数，将8次乘法，减少到7次。不要小看这减少的一次，每递归计算一次，效率就可以提高1/8，比如一个大的矩阵递归5次后，（7/8）5=0.5129，效率提升一倍。不过，这只是理论值，实际情况中，有隐含开销，并不是最常用算法。矩阵是稀疏矩阵时，为稀疏矩阵设计的方法更快。所以，稠密矩阵上的快速矩阵乘法实现一般采用Str
43、assen算法。Algorithms Design Techniques and Analysis6.8.4 三个算法的比较三种算法所做的算术运算的次数乘法加法复杂度传统算法.n3n3-n2(n3)递归方法.n3n3-n2(n3)STRASSEN算法.nlog76 nlog7-6 n2(nlog7)Algorithms Design Techniques and Analysis6.9 最近点对问题 问题:设S是平面上n个点的集合，在这一节中，我们考虑在S中找到一个点对p和q的问题，使其相互距离最短。换句话说，希望在S中找到具有这样性质的两点p1=(x1,y1)和p2=(x2,y2)，使它们间
44、的距离在所有S中点对间为最小。22122121)()(),(yyxxppdAlgorithms Design Techniques and Analysis最近点对问题 蛮力算法就是简单地检验所有可能的n(n-1)/2个距离并返回最短间距的点对。耗费(n2)的时间 我们将运用分治设计技术描述一个时间复杂性为(nlogn)的算法来解决最近点对间题。Algorithms Design Techniques and Analysis分治方法 Sort:第一步是以x坐标增序对S中的点排序 Divide:S点集被垂直线L大约划分成两个子集Sl和Sr，使|Sl|=|S|/2，|Sr|=|S|/2，设L是经
45、过x坐标Sn/2的垂直线，这样在Sl中的所有点都落在或靠近L的左边，而所有Sr中的点落在或靠近L的右边。Conquer:现在按上述递归地进行，两个子集Sl和Sr的最小间距l和r可分别计算出来。Combine:组合步骤是把在Sl中的点与Sr中的点之间的最小间距计算出来。最后所要求的解是l，r 和.中的最小值。Algorithms Design Techniques and Analysis基本思想sortdivideconquercombine比较这三个距离，返回最小值lrAlgorithms Design Techniques and Analysis 怎样合并结果，这一步的关键在于计算，计算
46、Sl中的每个点与Sr中每个点之间的距离的朴素方法需要(n2)。n设=minl,r，如果最近点对由Sl中的某个点pl与Sr中的某个点pr组成，则pl和pr一定在划分线L的距离内。这样，如果令Sl和Sr分别表示为在线L距离内的Sl和Sr 中的点，则pl一定在Sl中，pr一定在Sr中。Algorithms Design Techniques and Analysis假设 ，则存在两点plSl和prSr，有d(pl,pr)=，从而pl和pr之间的垂直距离不超过 因为pl，pr这两点都在以垂直线L为中心的2矩形区内或其边界上设T是两个垂直带内的点的集合如果在2矩形区内，任意两点间的距离一定不超过，则这个
47、矩形最多能容纳8个点，其中至多4个点属于Sl，4个点属于Sr。TLSlSr Algorithms Design Techniques and Analysis分治方法 观察结论6.5 T中的每个点最多需要和T中的7个点进行比较。上述的观察结论仅给出与T中每个点p的比较点数的上界，而没有给出哪些点与P比较的任何信息。稍想一下，即可知P一定是与T中临近的点比较。为了找到这样的相邻点，我们借助于以r坐标的递增序对T中的点重新排序，然后，不难看出只需对T中每个点P，与它们的Y坐标递增序下的7个点比较。Algorithms Design Techniques and Analysis时间复杂度排序S中的
48、点需要(nlogn)时间。把点划分成Sl和Sr子集需要D(1)时间，因为此时点已排序了。至于组合步骤，我们可以看到它包含对T中点的排序和每点与其他至多7个点做比较，排序耗费O(nlogn),时间，并存在至多7n次比较，这样组合步骤最坏情况下需要(n log n)时间。注意如果点数为3，则计算它们间最小间距只需要做三次比较，算法执行的递推关系变为：)log()(3log22 3321(2nnnTn)if n(n)nT(if n if n n)T Algorithms Design Techniques and Analysis时间复杂度 在组合步骤中，每次需要对T排序，现在只需要在(n)时间里从
49、数组Y中提取它的元素，这样递推式变为：12(33 ()(log)22()3 if nT n)if nT nnnT(n)n if n Algorithms Design Techniques and Analysis 算法6.7 CLOSESTPAIR输入:平面上n个点的集合S。输出:S中两点的最小距离。1.以x坐标增序对S中的点排序。2.序Y以y坐标增序对S中的点排序。3.cp(1,n).过程cp(low,high)1.if high-low+1 3 then 用直接方法计算2.else 3.mid(low+high)/24.x0 x(Smid)5.lcp(low,mid)6.rcp(mid+
50、1,high)7.midl,r8.k0 To be continuedAlgorithms Design Techniques and Analysis过程 cp(low,high)9.for i1 to n 从Y中抽取T10.if|x(Yi)-x0|then11.kk+112.TkYi13.end if 14.end for15.216.for i1 to k-117.for ji+1 to mini+7,k18.if d(Ti,Tj)then d(Ti,Tj)19.end for20.end for21.min,22.end if23.return Algorithms Design Te
