算法分析与设计6

《算法分析与设计6》由会员分享，可在线阅读，更多相关《算法分析与设计6（24页珍藏版）》请在装配图网上搜索。

1、陈卫东华南师范大学计算机科学系Algorithms:Design Techniques and Analysis 算法设计技巧与分析算法设计技巧与分析 Chapter 6 Divide and ConquernThe Divide and Conquer Paradigmn6.1 Introductionn6.2 Binary Searchn6.3 Merge Sortn6.4 The Divide and Conquer Paradigm n6.5 Selection:Finding the Median and kth Smallest Elementn6.6 Quick Sortn6.7

2、 Multiplication of Large Integersn6.8 Matrix Multiplicationn6.9 The Closest Pair ProblemThe Divide and Conquer Paradigm 6.1 Introductionn问题：问题：在序列A1.n中找最小和最大元素。n算法思想：算法思想：在序列在序列A1n中找最小和最大元素中找最小和最大元素x,y if(n=2)直接比较得结果直接比较得结果;else 在序列在序列A1mid中找最小和最大元素中找最小和最大元素x1,y1;在序列在序列Amid+1.n中找最小和最大元素中找最小和最大元素x2,y

3、2;x=minx1,x2;y=maxy1,y2;nAlgorithm 6.1 MINMAXn算法分析：算法分析：算法的比较次数为：算法的比较次数为：3n/2-2The Divide and Conquer Paradigm 6.2 Binary Search(二分检索二分检索)n问题：问题：在序列A1.n中查找x，若找到返回下标，否则返回0。n算法思想：算法思想：在序列在序列A1n中找中找x if 序列长度序列长度n为为0，返回，返回0;else case x=Amid:返回返回mid;case xAmid:在序列在序列Amid+1.n中找中找x;nAlgorithm 6.2 BINARYSE

4、ARCHERCn算法分析：算法分析：算法的最坏时间复杂度：算法的最坏时间复杂度：(log n)The Divide and Conquer Paradigm 6.3 Merge Sort(归并排序归并排序)n问题：问题：将序列A1.n中元素按照升序排序。n算法思想：算法思想：将序列将序列A1n中元素排序中元素排序 if 序列长度序列长度n1 将序列将序列A1mid中元素排序中元素排序;将序列将序列Amid+1.n中元素排序中元素排序;归并两个有序序列归并两个有序序列A1mid和和Amid+1.n；nAlgorithm 6.3 MERGESORTn算法分析：算法分析：算法的时间复杂度：算法的时间

5、复杂度：(nlog n)The Divide and Conquer Paradigm 6.4 The Divide and Conquer Paradigm （分而治之法的基本模式）n分而治之法模式的三个主要步骤：分而治之法模式的三个主要步骤：nThe divide stepnThe conquer stepnThe combine stepThe Divide and Conquer Paradigm 6.4 The Divide and Conquer Paradigm n分而治之法算法的模式分而治之法算法的模式n若问题实例若问题实例I大小大小“较小较小”，则直接求解并返回，则直接求解并

6、返回结果；否则进行下一步；结果；否则进行下一步；n（divide）将）将I分成分成m个大小基本相同的子实例个大小基本相同的子实例I1,I2,Im；n（conquer）对于每个子实例递归地求解得到）对于每个子实例递归地求解得到它们的解；它们的解；n（combine）将子实例的解合并得到实例）将子实例的解合并得到实例I的解的解实例实例I:？分解实例实例I 1:？实例实例I2:？实例实例I m:？分解递归求解实例实例I 1:y1实例实例I 2:y2实例实例I m:ym合并实例实例I:y分治法的直观描述6.5 Selection:Finding the Median and the kth Small

7、est Elementn选择问题选择问题(the selection problem)找出序列A1.n中的第k小元素(the kth smallest element)。特别地，当k=n/2时，即找中值元素(the median element)。n算法算法1：排序法：排序法n时间复杂度时间复杂度:(nlog n)6.5 Finding the kth Smallest Elementn算法算法2：分治法：分治法（最坏情况时间为（最坏情况时间为(n2)）n算法思想算法思想 对于集合A(1:n)中的元素，用其中某元素v进行划分：A1=a|av且aA。case|A1|k：问题归结为在A1中找第k小

8、元素；case|A1|+|A2|=k：v就是第k小元素；case|A1|+|A2|k：问题归结为在A3中找第k-|A1|-|A2|小元素。对于第一、第三种情形，在A1或A3上重复上述过程直到找到所要找的元素为止。n时间复杂度分析：时间复杂度分析：the worst case:(n2)6.5 Finding the kth Smallest Elementn算法算法3：分治法：分治法（最坏情况时间为（最坏情况时间为(n)）n算法思想：算法思想：在上述算法中，在上述算法中，划分元素为二次取中值得到划分元素为二次取中值得到，这样就保证了子问题这样就保证了子问题A1或A3的大小变为的大小变为A大小的大

9、小的p倍（倍（p为常数且为常数且0p1）。）。由此所得算法的最坏情况时间为由此所得算法的最坏情况时间为(n)。nAlgorithm 6.4 SELECT 6.5 Finding the kth Smallest Elementn算法算法3nAnalysis of the selection algorithm T(n)T(n/5)+T(3n/4)+cn,n44;T(n)c,n1，且T(1)=d 由此得到：T(n)=(nlog 3)=O(n1.59)6.8 Matrix Multiplicationn问题：问题：n设设A和和B是是n n矩阵，求其乘积矩阵，求其乘积C=AB.n算法算法1（The

10、traditional algorithm）n算法思想 n时间复杂度：(n3)n3次乘法和n3 n2次加法n算法算法2（Recursive version）n算法思想n时间复杂度分析：T(n)=8T(n/2)+4(n/2)2a,n=2，且T(1)=m。由此得到:T(n)=(n3)n3次乘法和n3 n2次加法 6.8 Matrix Multiplicationn算法算法3（Strassens algorithm）n算法思想n时间复杂度分析：T(n)=7T(n/2)+(9a/2)n2,n=2，且T(1)=m。由此得到:T(n)=(nlog7)=O(n2.81)nComparisions of th

11、e three algorithms6.9 The Closest Pair Problem (最近点对问题最近点对问题)n 问题问题 在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其它几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空中移动的一个点来看待，则具有最大碰撞危险的2架飞机就是空中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。给定平面上n个点(xi,yi)，1in，找出其中的一对点，使得在n个点的所有点对中，该点对的距离最短。6.9 The Closest Pa

12、ir Problem (最近点对问题最近点对问题)n 算法算法思想思想n算法一（直接法直接法）：通过检查所有的n(n-1)/2对点，并计算每一对点的距离，即可找出距离最近的一对点。这种方法所需的时间为O(n2)。n算法二（分治法分治法）：1）当n较小时，用直接法着最近点对；2）当n较大时，将点集分成大致相等的两部分A和B，（递归地）确定A和B中的最近点对，确定一点在A中，另一点在B中的最近点对，从上面得到的三对点中，找出距离最小的一对点。根据下面的过程，容易知道该算法所需时间为O(nlog n)。6.9 The Closest Pair Problem (最近点对问题最近点对问题)在上述分解的

13、步骤中，可在点集中横坐标x的中值处画一条垂线来划分点集。在递归地求解子问题时，关键是确定第三种情况：一点在A中，一点在B中的最近点对。这一步骤能若有效解决，则合并步骤相当简单。如果用一一比较法解它，则花费的时间很多，从而使得整个算法的时间为O(n2),这与直接法相同。这里我们将它与合并步骤同时考虑。设是A的最近点对的距离和B的最近点对的距离中最小者。若第三种情况中的最近点对距离比小，则其中每点必然在距离垂线距离的区域内。如下图所示。6.9 The Closest Pair Problem (最近点对问题最近点对问题)AB oooo RARB 对于RA中的每一点p，只需与位于RB中的一个大小为2的区域中的点相比即可。有鸽笼原理可知，该区域至多有6个点。即RA中的每一点至多与6个点相比即可求出第三种情况下的最近点对的点距。比一一比较法省时间，它的时间为O(n)。如下图所示。p RARB 6.9 The Closest Pair Problem (最近点对问题最近点对问题)作业题：作业题：n6.39n6.44n6.48