第六讲-分治-算法设计与分析课件.ppt

《第六讲-分治-算法设计与分析课件.ppt》由会员分享，可在线阅读，更多相关《第六讲-分治-算法设计与分析课件.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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算法算法6.1 MINMAX输入输入:n个整数元素的数组A1.n，n为2的幂。输出输出

3、:(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)/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

4、 Techniques and Analysis算法分析设C(n)表示算法在由n个元素(n是2的整数幂)组成的数组上执行的元素比较次数。见P112 定理 6.1 设数组A1.n包含n个元素，其中n是2的幂，则仅用3n/2一2次元素比较就能够在数组A中找出最大和最小元素。Algorithms Design Techniques and Analysis6.2 二分搜索 问题描述在数组A1.n中搜索已知元素x基本思想将一个给定的元素x与一个已排序数组Alow.high.的中间元素做比较如果x Amid，则放弃Alow.mid，而对Amid+1.high重复实施相同的方法.Algorithms De

5、sign Techniques and Analysis算法分析 假设 为了求出算法的执行时间，我们计算元素间的比较次数，因为这是一个基本运算，也就是说，算法的执行时间与完成元素间比较次数是成比例的(见1.11.2节)。我们将假定每个三向比较当做一次比较来计算推导见P113 定理6.2算法BINARYSEARCHREC在n个元素组成的数组中搜索某个元素所执行的元素比较次数不超过logn+1。算法BINARYSEARCHREC的时间复杂性是O(logn)。算法递归深度为O(log n)，并且由于每个递归层次需要(l)的空间，本算法所需的空间总量是(log n)。和递归算法相反，其迭代形式算法仅需

6、要(l)空间Algorithms Design Techniques and Analysis6.3 合并排序BOTTOMUPSORT:在每一层中，我们有已排序的序列对，同时它们两两被合并而得到较大的排序序列。沿着树一层一层向上继续这个过程，直到到达根为止，这最后的序列是已经排序好的。让我们从反向来考虑，是否能用自顶向下取代自底向上？Algorithms Design Techniques and Analysis算法算法6.3 Mergesort输入输入:n个元素的数组A1.n。输出输出:按非降序排列的数组A1.n。1.mergesort(A,1,n)过程 mergesort(A,low,h

7、igh)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 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,

8、2)MS(3,4)MS(3,3)M(3,3,3)MS(4,4)M(4,4,4)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?这个调用链对应于树的前序遍历:访问根、左子树和右子树。计算却对应于树的后序遍历:访问左子树，右子树，最后是根。为了实现这个遍历，用一个

9、栈来存储每次调用过程的局部数据。在算法BOTPOMUPSORT中，合并是一层接一层进行的;而在算法MERGESORT中，合并是以后序遍历的方式进行的。两种算法的区别仅在于合并的次序，因此，当n是2的幂时，由算法MERGESORT执行的比较次数和算法BOTIOMUPSORT执行的次数相同。Algorithms Design Techniques and Analysis合并算法分析最大比较次数：Algorithms Design Techniques and Analysis合并算法分析如果n是任意的正整数(不必是2的幂)，对于由算法MERGESORT执行的元素比较次数：定理6.3 算法MERG

10、ESORT对一个n个元素的数组排序所需的时间是(nlogn)，空间是(n)。Algorithms Design Techniques and Analysis6.4 分治范式P117一般来说分治范式由以下的步骤组成划分步骤。在算法的这个步骤中，输入被分成p 1个部分，每个子实例的规模严格小于n，n是原始实例的规模。尽管比2大的其他小的常数很普遍，但P的最常用的值是2。治理步骤。如果问题的规模大于某个预定的阈值n。，这个步骤由执行P个递归调用组成，阈值是由算法的数学分析导出的组合步骤。这个步骤是组合P个递归调用的解来得到期望的输出值。Algorithms Design Techniques an

11、d Analysis一般而言，分治算法有以下形式如果实例I的规模是“小”的，则使用直接的方法求解问题并返回其答案，否则继续做下一步。把实例I分割成P个大小几乎相同的子实例I1,I2,.,Ip。对每个子实例Ij，1jp,递归调用算法，并得到P个部分解。组合P个部分解的结果得到原实例I的解，返回实例I的解。Algorithms Design Techniques and Analysis6.5 寻找中项和第k小元素 选择问题在一个包含n个元素的集合中寻找第k个最小元素。(中值是第n/2个最小元素)直接方法:对所有的元素排序并取出中间一个元素，这个方法需要(nlogn)时间，因为任何基于比较的排序过

12、程在最坏的情况下必须至少要花费这么多时间 Can we find an efficient method in optimal linear time?能否在最优线性时间内找到更快的算法？Algorithms Design Techniques and AnalysisSELECT 算法基本思想首先，如果元素个数小于预定义的阈值44，则算法使用直接的方法计算第k小的元素，至于如何选择阂值在以后的算法分析中将会清楚。下一步把n个元素划分成n/5组，每组由5个元素组成，如果n不是5的倍数，则排除剩余的元素，这应当不影响算法的执行。每组进行排序并取出它的中项即第三个元素接着将这些中项序列中的中项元素

13、记为mm，它是通过递归计算得到的。将数组A中的元素划分成三个数组:A1,A2,A3，其中分别包含小于、等于和大于mm的元素。最后，求出第k小的元素出现在三个数组中的哪一个，并根据测试结果，算法或者返回第k小的元素，或者在A1 or A3上递归。Algorithms Design Techniques and Analysis算法算法6.4 SELECT输入输入: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

14、)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|+|A2|k:return mm|A1|+|A2|k:return select(A3,1,|A3|,k-|A1|-|A2|)8.end case Algorithms Design Techniques and Analysis例子为方便起见，让我们暂时

15、将算法中的阈值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 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 16part

16、ition8 11 32 13 12 6 5 71417 25 16 22 23discardAlgorithms Design Techniques and Analysis例子17 25 16 22 23A1115sort16 17 22 23 25Succeed!The result is A13=22Algorithms Design Techniques and Analysisselection算法分析所有围在矩形W 中的元素是小于或等于mm的，所有围在矩形x中的元素是大于或等于mm 的。设A1表示小于或等于mm的元素集，A3是大于或等于mm的元素集这个算法中，A1是严格小于mm的

17、元素集，A3是严格大于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)时间。

18、由以上的分析，步骤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)时间找出。Algorithms Design Techniques and Analysis6.6 快速排序快速排序是另外一种排序算法,该排

19、序算法具有(nlogn)的平均运行时间这个算法优于MERGESORT算法的一点是它在原位上排序，即对于被排序的元素，不需要辅助的存储空间。Algorithms Design Techniques and Analysis6.6.1 划分算法基本思想设Alow.high是一个包含n个数的数组，并且x=Alow我们考虑重新安排数组A中的元素的问题，使得小于或等于x的元素在x的前面，随后x又在所有大于它的元素的前面经过数组中元素改变排列后，对于某个w，lowwhigh，x在Aw 中。例如,如果A=,3,9,2,7,1,8；则经过重新排列其中的元素后，得到 A=1,3,2,7,9,8 其中 w=4。5

20、5Algorithms 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.输出:(1)如有必要，输出按上述描述的重新排列的数组A。(2)划分元素Alow的新位置w。1.ilow2.

21、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 Analysis算法分析观察结论6.3 由算法SPLIT执行的元素比较次数恰好是n-1，这样它的时间复杂性为(n)。最

22、后注意到算法仅仅用到一个额外空间用于存储它的局部变量，因此算法的空间复杂性为(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 递归地排序，自动产生整个排序数组Algorithms Design Techniques and Analysis算法6.6 QIUCKSO

23、RT输入: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.4631872523148765231123113376587685576576766766Success!Algori

24、thms Design Techniques and AnalysisMERGESORT 和 QUICKSORT算法SPLIT和算法QUICKSORT的关系类似于算法MERGE和算法MERGESORT的关系。两个排序算法都由名为SPLIT和MERGE的算法之一的一系列调用组成。在算法MERGESORT中，合并排序序列属于组合步骤，而在算法QUICKSORT中的划分过程则属于划分步骤。事实上，在算法QUICKSORT中组合步骤是不存在的。Algorithms Design Techniques and Analysis6.6.3 快速排序算法分析空间复杂度:虽然算法不需要辅助空间存储数组元素，但

25、算法还是至少需要(n)的空间，工作空间在(logn)和(n)之间变化。这是因为在每次递归调用中，表示下一次要排序的数组右边部分的左右界w1和high必须保存。Algorithms Design Techniques and Analysis6.6.3.1 最坏情况的行为定理6.5 在最坏的情况下，算法QUICKSORT的运行时间是(n2)，然而如果总是选择中项作为主元，它的时间复杂性是(nlogn)。推导见P116Algorithms Design Techniques and Analysis6.6.3.2 平均情况的行为 假设假定对于数1，2，n的i个排列中的每一个排列的出现是等可能性的，

26、这一点确保了在数组中的每个数以同样可能作为第一个元素，并被选为主元，也就是说，数组A中的任意元素被选为主元的概率是1/n.设C(n)表示对大小为n的输入数据算法所做的平均比较次数，根据观察结论6.3，得到：步骤2恰好耗费n-1次比较；步骤3和步骤4分别耗费了C(w-1)和C(n-w)次比较；因此总的比较次数为：Algorithms Design Techniques and Analysis因为 因此如果用n-1代替n，得到：推导见P1176.6.3.2 平均情况的行为Algorithms Design Techniques and Analysis等式6.3减去等式6.4，再重新排列各项得到

27、现在把变量更换为一个新的变量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 大整数乘法我们假定大小一定的整数相乘需要耗费定量的时间，而当两个任意长的整数相乘时，这个假定就不再有效了对于处理不定长数的算法的数据输入，通常是按二进制的位数来计算的(或按二进制数字来计算)设u和v是两个n位的整数，

28、传统的乘法算法需要(n2)数字相乘来计算u和v的乘积。Is there much more efficient method?Algorithms Design Techniques and Analysis6.7 大整数乘法设u和v都是n位的二进制整数，现在要计算它们的乘积u*v。我们可以用小学所学的方法来设计一个计算乘积u*v的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积u*v。下面我们用分治法来设计一个更有效的大整数乘积算法。我们将n位的二进制整数u和v各分为2段，每段的长为n/2位(为简单起见，假设

29、n是2的幂)，Algorithms Design Techniques and Analysis分治技术假定n是2的幂.wxyzu和v的乘积可以计算为：时间复杂度函数为：递推式的解：n/2n/2Algorithms Design Techniques and Analysis分治技术现在考虑：我们得到：时间复杂度是：递推式的解是：Algorithms Design Techniques and Analysis6.8 矩阵乘法 两个矩阵 A，B：A 的列数等于 B 的行数，则A、B可以相乘。即，如果 A=（aij）是一个m*n的矩阵，B=（bjk）是一个 n*p 的矩阵，则它们的乘积 C=AB

30、 是 m*p 矩阵 C=（cik）。A23B32C22Algorithms Design 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).Is there much more efficient method?Algorith

31、ms Design Techniques and Analysis6.8.2 递归方法假定n=2k，k 0，如果n2，则A，B和C可分别分成4个大小为n/2n/2的子矩阵用分治方法来计算C的组成：Algorithms Design Techniques and Analysis递归方法计算量总耗费是：最终结果：观察结论 6.4递归方法需要n3次乘法运算和n3-n2次加法运算，这些刚好和前面传统方法所讲述的一样。两种算法的区别仅仅在于矩阵元素相乘的次序上，其他方面是一样的Algorithms Design Techniques and Analysis6.8.3 STRASSEN算法基本思想增加

32、加减法的次数来减少乘法次数和Algorithms Design Techniques and AnalysisSTRASSEN算法 基本思想我们首先计算以下的乘积接着从一下面式子计算出CAlgorithms Design Techniques and Analysis时间复杂度 算法用到的加法是18次，乘法是7次，对于其运行时间产生以下递推式（P121）或即运行时间为：Algorithms Design Techniques and Analysis时间复杂度Strassen算法的高效之处，就在于，它成功的减少了乘法次数，将8次乘法，减少到7次。不要小看这减少的一次，每递归计算一次，效率就可以

33、提高1/8，比如一个大的矩阵递归5次后，（7/8）5=0.5129，效率提升一倍。不过，这只是理论值，实际情况中，有隐含开销，并不是最常用算法。矩阵是稀疏矩阵时，为稀疏矩阵设计的方法更快。所以，稠密矩阵上的快速矩阵乘法实现一般采用Strassen算法。Algorithms Design Techniques and Analysis6.8.4 三个算法的比较三种算法所做的算术运算的次数乘法加法复杂度传统算法.n3n3-n2(n3)递归方法.n3n3-n2(n3)STRASSEN算法.nlog76 nlog7-6 n2(nlog7)Algorithms Design Techniques and

34、 Analysis6.9 最近点对问题 问题:设S是平面上n个点的集合，在这一节中，我们考虑在S中找到一个点对p和q的问题，使其相互距离最短。换句话说，希望在S中找到具有这样性质的两点p1=(x1,y1)和p2=(x2,y2)，使它们间的距离在所有S中点对间为最小。Algorithms Design Techniques and Analysis最近点对问题蛮力算法就是简单地检验所有可能的n(n-1)/2个距离并返回最短间距的点对。耗费(n2)的时间我们将运用分治设计技术描述一个时间复杂性为(nlogn)的算法来解决最近点对间题。Algorithms Design Techniques and

35、 Analysis分治方法Sort:第一步是以x坐标增序对S中的点排序Divide:S点集被垂直线L大约划分成两个子集Sl和Sr，使|Sl|=|S|/2，|Sr|=|S|/2，设L是经过x坐标Sn/2的垂直线，这样在Sl中的所有点都落在或靠近L的左边，而所有Sr中的点落在或靠近L的右边。Conquer:现在按上述递归地进行，两个子集Sl和Sr的最小间距l和r可分别计算出来。Combine:组合步骤是把在Sl中的点与Sr中的点之间的最小间距计算出来。最后所要求的解是l，r 和.中的最小值。Algorithms Design Techniques and Analysis基本思想sortdivid

36、econquercombine比较这三个距离，返回最小值lrAlgorithms Design Techniques and Analysis怎样合并结果，这一步的关键在于计算，计算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)

37、=，从而pl和pr之间的垂直距离不超过 因为pl，pr这两点都在以垂直线L为中心的2矩形区内或其边界上设T是两个垂直带内的点的集合如果在2矩形区内，任意两点间的距离一定不超过，则这个矩形最多能容纳8个点，其中至多4个点属于Sl，4个点属于Sr。TLSlSr Algorithms Design Techniques and Analysis分治方法 观察结论6.5 T中的每个点最多需要和T中的7个点进行比较。上述的观察结论仅给出与T中每个点p的比较点数的上界，而没有给出哪些点与P比较的任何信息。稍想一下，即可知P一定是与T中临近的点比较。为了找到这样的相邻点，我们借助于以r坐标的递增序对T中的点

38、重新排序，然后，不难看出只需对T中每个点P，与它们的Y坐标递增序下的7个点比较。Algorithms Design Techniques and Analysis时间复杂度排序S中的点需要(nlogn)时间。把点划分成Sl和Sr子集需要D(1)时间，因为此时点已排序了。至于组合步骤，我们可以看到它包含对T中点的排序和每点与其他至多7个点做比较，排序耗费O(nlogn),时间，并存在至多7n次比较，这样组合步骤最坏情况下需要(n log n)时间。注意如果点数为3，则计算它们间最小间距只需要做三次比较，算法执行的递推关系变为：Algorithms Design Techniques and An

39、alysis时间复杂度 在组合步骤中，每次需要对T排序，现在只需要在(n)时间里从数组Y中提取它的元素，这样递推式变为：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+1,high

40、)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 Techniques and AnalysisCLOSESTPAIR的时间复杂度 定理6.7 假定有平面上n个点的集合S，算法CLOSESTPAIR在(n logn).时间内找到S中具有最小间距的一个点对。Algorithms Design Techniques and AnalysisExercises6.10（b）6.136.146.266.36（c）