《算法引论》PPT课件

《《算法引论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京理工大学算法设计与分析AlgorithmDesignandAnalysis孙廷凯suntingkai@njust.edu.cn南京理工大学课程内容(32学时)常用的算法设计策略(包括分治策略、动态规划、贪心策略、回溯法、随机算法等)算法复杂度分析方法(计算迭代次数、使用递归方程、频度分析等)南京理工大学课程要求掌握常用的算法设计策略、算法复杂度分析方法授课方式：讲授考核方式：南京理工大学教材《算法设计技巧与分析》，M.H.Alsuwaiyel著,电子工业出版社，吴伟昶等译，2004南京理工大学相关参考文献AlgorithmDesignT

2、echniquesandAnalysis,M.H.Alsuwaiyel.(影印本).电子工业出版社.2003算法导论(第2版)，ThomasH.Cormen等著，潘金贵等译，机械工业出版社，2006.计算机算法设计与分析(第3版),王晓东,电子工业出版社,2007.算法设计与分析，王红梅编著，清华大学出版社，2006.南京理工大学1算法引论历史背景算法复杂度与渐近分析方法如何估计算法的复杂度算法复杂度分析的意义南京理工大学历史背景阶段1：二十世纪30年代，能否使用一个有效的过程来求解一个问题(相当于现在算法的概念)一直是人们所关注的。当时的

3、焦点是将问题进行分类：可解或是不可解。关注问题是否可以求解的领域称为可计算理论(computabilitytheoryortheoryofcomputation)。出现了一系列的计算模型，例如：calculusofChurch、PostmachinesofPost、TuringmachinesofTuring、RAMmodelofcomputation。阶段2：随着数字计算机的出现，人们越来越关注于那些可求解的问题。一开始，人们满足于能够在一定的时间内解决一个特定的问题，而不去关注所需要的资源。慢慢地，人们需要考虑在有限资源的条件下高效地解

4、决问题。这就导致了计算复杂度(computationalcomplexity)这一新学科的诞生。在这个领域，主要是研究解决可求解问题时所需要的资源，主要是时间和空间复杂性。有时候，其他的资源也需要考虑，例如，通信代价、需要使用的处理器的个数(使用并行计算模型)等等。南京理工大学引例：搜索问题给定已经排好序(不妨假设为非降序)的n个元素A[1…n],现在要判定一个给定的元素x是否在此数组中出现。方法1：顺序搜索方法2：二分搜索南京理工大学二分搜索算法输入：非降序排列的数组A[1…n]和元素x输出：如果x=A[j],1jn,则输出j,否则输

5、出0.1.low←1;high←n;j←02.while(lowhigh)and(j=0)3.mid←(low+high)/24.ifx=A[mid]thenj←mid5.elseifx

6、，剩余元素的个数是n/2j-1或者找到x，或者程序在子序列长度达到1时终止搜索,此时n/2j-1=11n/2j-1<22j-1n<2jlogn

7、有限。程序与算法的区别：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性性质。南京理工大学算法的复杂度复杂度：算法运行时需要耗费计算机资源的量，可以分为时间复杂度和空间复杂度。算法复杂度依赖于三个方面：待求解问题的规模、算法的输入和算法本身。用n,I,A分别表示问题的规模、算法的输入和算法本身，用表示C复杂度，则有：C=F(n,I,A)。如果将时间复杂度和空间复杂度分开，则有T=T(n,I,A)和S=S(n,I,A)。通常，我们让A隐藏在复杂度函数名中，所以有T=T(n,I)和S=S(n,I)。由于时间复杂度和空间复杂度概

8、念类似，计量方法类似，且空间复杂度分析相对简单，因此本课程主要讨论算法的时间复杂度。南京理工大学T=T(n,I)的具体化假设计算机提供k种元运算，分别记为O1,O2,…,Ok。所