算法设计与分析课件第1章 节 算法设计与分析4.ppt

算法设计与分析;;许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习必威体育精装版的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。——摘自“算法的力量” ;;; ; ; ;;;;递归与分治 动态规划 贪心算法 回朔法 分支限界法 随机化算法;;第1章 算法概述;学习要点:;算法(Algorithm);程序(Program);问题求解(Problem Solving);;; 算法的复杂性分析具有极重要的实际意义. 有许多实际应用问题,理论上是有计算机解的,但由于求解所需的时间或或空间耗费巨大,如成千上万年,以至于实际上无法办到;对有些时效性很强的问题,如实时控制,即使算法执行时间很短,只有一两秒,也可能是无法忍受的.; 描述算法的方式一般有三种:自然语言,流程图,伪代码语言. 伪代码描述介于自然语言与程序设计语言之间。因为算法描述的目的是使学习者易于理解和掌握算法的基本思想和步骤，并不是提供可直接上机的源代码,过去采用算法语言类pascal较多,近年多用c,c++,java描述,与数据结构相一致.;算法结构 ;算法结构 ;并行算法:并行计算机上执行的算法.; 算法的复杂性:指执行算法所消耗或占用的资源的数量 一个算法所需资源越多, 则它的复杂性越高,反之则低.; 考虑空间复杂性的理由 在多用户系统中运行时，需指明分给该程序的内存大小； 需预先知道计算机系统是否有足够的内存来运行该程序； 一个问题可能有若干个不同的内存解决方案，从中择取； 用空间复杂性估计一个程序可能解决的问题的最大规模。;算法的复杂性;算法复杂性分析 ; 算法的复杂性: 算法运行所需的时间和空间的数量. 显然,它与算法求解问题的规模n,算法的输入数I 及算法本身有关. ;算法效率与计算机的性能有关,但此因素对所有算法的影响相同;令 n: 问题规模 I: 输入数据 A: 算法本身 C: 算法的复杂性 则 C=f ( n, I, A ) ;设一台抽象计算机提供的元运算有k种, 记作 O1 ,…,Ok ; 设这些元运算每执行一次所需时间分别为 t1 ,…, tk ; 设在算法A中用到Oi的次数为 ei , i =1,…,k, 则 ei = ei ( n, I ) ;复杂性的计量;最好情况:Tmin(n) = T(n,I)= = = ;;可以想象,当一个问题的输入规模很大时,算法的结构又很复杂时,采用前面介绍的精确分析就显得过于繁琐，为降低算法分析的代价,同时又保证估算的精确度,引入一个简化的计算模型来评估算法的开销,称为渐进分析. 渐进分析是对问题的规模充分大的算法开销的估算。 ;复杂性的渐进性态; 当n充分大时用 代替T(n)作为算法复杂性的度量,以 简化分析;渐进性态的阶;1． 用来作比较的函数 g(n)应该尽量接近 f(n). 例如 3n+2=O(n2) 松散的界限；3n+2=O(n) 较好的界限 2． 不要产生错误界限。 例如 n2+100n+6，当 n3 时，n2+100n+6106n，由此 就认为 n2+100n+6＝O(n). 3． f(n)=O(g(n))不能写成 g(n)=O(f(n)) 因为两者并不等价。实际上，这里的等号并不是通常 相等的含义。 ;(2) 大?表示法 (算法运行时间的下限）; f (n) =?(g(n) )等价于 f(n)=O(g (n) ) 且 f(n)=?(g (n) ) 称函数f(n)与g(n) 同阶.;F(n)=O(g(n)); ;f(n) = ? (g(n));不同时间函数的增长率;不同时间复杂性函数的对比;不同时间复杂性函数的对比;多项式阶算法(有效算法):若算法的最坏情形时间复杂度 T(n)=O(nk); 指数阶算法:若算法的最坏情形时间复杂度T(n)=Ω(an) , a1. 这类算法可认为计算上不可行的算法.;算法复杂性分类:;提高计算速度对不同时间复杂性函数的影响对比;对规模较小的问题,决定算法工作效率的可能是算法的简单性而不是算法执行的时间.;1). 赋值,比较