算法引论.pptx

南京理工大学课程内容(32学时)常用的算法设计策略(包括分治策略、动态规划、贪心策略、回溯法、随机算法等)算法复杂度分析方法(计算迭代次数、使用递归方程、频度分析等)南京理工大学课程要求掌握常用的算法设计策略、算法复杂度分析方法授课方式:讲授考核方式:南京理工大学教材《算法设计技巧与分析》,,电子工业出版社,吴伟昶等译,2004南京理工大学相关参考文献AlgorithmDesignTechniquesandAnalysis,.(影印本).(第2版),,潘金贵等译,机械工业出版社,(第3版),王晓东,电子工业出版社,,王红梅编著,清华大学出版社,:二十世纪30年代,能否使用一个有效的过程来求解一个问题(相当于现在算法的概念)一直是人们所关注的。当时的焦点是将问题进行分类:可解或是不可解。putation)。出现了一系列的计算模型,例如:calculusofChurch、PostmachinesofPost、TuringmachinesofTuring、putation。阶段2:随着数字计算机的出现,人们越来越关注于那些可求解的问题。一开始,人们满足于能够在一定的时间内解决一个特定的问题,而不去关注所需要的资源。慢慢地,人们需要考虑在有限资源的条件下高效地解决问题。plexity)这一新学科的诞生。在这个领域,主要是研究解决可求解问题时所需要的资源,主要是时间和空间复杂性。有时候,其他的资源也需要考虑,例如,通信代价、需要使用的处理器的个数(使用并行计算模型)等等。南京理工大学引例:搜索问题给定已经排好序(不妨假设为非降序)的n个元素A[1…n],现在要判定一个给定的元素x是否在此数组中出现。方法1:顺序搜索方法2:二分搜索南京理工大学二分搜索算法输入:非降序排列的数组A[1…n]和元素x输出:如果x=A[j],1jn,则输出j,←1;high←n;j←(lowhigh)and(j=0)←(low+high)/2=A[mid]thenj←<A[mid]thenhigh←mid-←mid+:比较1次最坏情形:比较logn+1次每次循环都要抛弃一些元素,例如第二次循环时,剩余元素为A[1…mid-1]或A[mid+1…n],不妨设为A[mid+1…n],则剩余的元素个数是n/2第j次while循环时,剩余元素的个数是n/2j-1或者找到x,或者程序在子序列长度达到1时终止搜索,此时n/2j-1=11n/2j-1<22j-1n<2jlogn<jlogn+1j=logn+1南京理工大学算法及其性质算法是对问题求解过程的准确描述,由有限条指令组成,这些指令能在有限时间内执行完毕并产生确定性的输出。算法需满足的4个性质:输入:零个或多个外部量作为输入。输出:至少产生一个量作为输出,它(们)与输入量之间存在某种特定的联系。确定性:组成算法的每条指令都是清晰、无歧义的。有限性:每条指令的执行次数有限,执行每条指令的时间也有限。程序与算法的区别:程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性性质。