算法设计与分析3.ppt

《算法设计与分析3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3Divide-and-conquerAlgorithms3.1Divide-and-ConquertheoryMainidea:Theybreaktheproblemintoseveralsubproblemsthataresimilartotheoriginalproblembutsmallerinsize,solvethesubproblemsrecursively,andthencombinethesesolutionstocreateasolutiontotheoriginalproble

2、m.Thedivide-and-conquerapproachinvolvesthreestepsateachleveloftherecursion:Dividetheproblemintoanumberofsubproblems.Conquerthesubproblemsbysolvingthemrecursively.Ifthesubproblemsizesaremallenough,however,justsolvethesubproblemsinastraightforwardmanner.Combine

3、thesolutionstothesubproblemsintothesolutionfortheoriginalproblem.Chapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithmsChapter3Divide

4、-and-conquerAlgorithms二分搜索技术Chapter3Divide-and-conquerAlgorithmsKnuth“TheArtofComputerProgramming:SortingandSearching”19461962Bentley“WritingCorrectPrograms”90%2hoursChapter3Divide-and-conquerAlgorithms3.2合并排序1.算法的基本思想:·Divide：把n元素序列分为2个元序列。·Conquer:使用Merge-s

5、ort递归地排序2个子序列。·Combine:合并2个Sorted子序列，产生n元素的有序序列。Chapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithms2.算法定义输入：Ap,r：欲排序数据在数组A中。输出：Ap,r：排序后的数据。方法：Merge-Sort(A,p,r){if(p

6、*Merge算法十分简单，需要O(n)次比较。*若要排序存储在数组A的n个数,只需调用Merge-Sort(A,1,n)。Chapter3Divide-and-conquerAlgorithms2.算法定义输入：Ap,r：欲排序数据在数组A中。输出：Ap,r：排序后的数据。方法：Merge-Sort(A,p,r){if(p

7、*若要排序存储在数组A的n个数,只需调用Merge-Sort(A,1,n)。Chapter3Divide-and-conquerAlgorithms3.Merge-Sort的分析·Ifn=1,T(n)=(1)·Divide阶段的时间复杂性:D(n)=(1)·Conquer阶段的时间复杂性:2T(n/2)·Combine阶段的时间复杂性:C(n)=(n)Chapter3Divide-and-conquerAlgorithms3.3大整数的乘法Chapter3Divide-and-conquerAlgorith

8、msChapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithms3.4矩阵乘法Chapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorithmsChapter3Divide-and-conquerAlgorith