1 课程概述.pdfVIP

算法分析 陈卫东 chenwd@scnu.edu.cn 华南师范大学计算机学院 2009-10-9 1. 算法分析的基本方法 1.1. 算法及其特性 1.2. 衡量一个算法性能的好坏的标准 1.3. 算法的时间和空间复杂度 1.4. 算法分析(Algorithm Analysis) 1.4.1. 分析算法时间复杂度的基本步骤 1.4.2. 算法时间复杂度的有关概念 1.4.3. 分析、求解算法复杂度的方法 1.5. 最优算法(optimal algorithm) W.D.Chen South China Normal University 1 1.1. 算法及其特性 算法 （algorithm ）： 算法就是一组有穷的规则，它们规定了解决某一 特定类型问题的一系列运算。 算法的五个特性： 确定性 能行性 有穷性 输入 输出 W.D.Chen South China Normal University 2 1.2. 衡量算法性能的标准 衡量算法性能一般有下面几个标准 正确性 易读性 健壮性 算法的时间和空间性能：高效率和低存储空间 我们这里主要讨论算法的时间和空间性能，并以此作为衡 量算法性能的重要标准。而且我们主要侧重于时间方面。 W.D.Chen South China Normal University 3 1.3. 算法的时间和空间复杂度 时间复杂度 （Time Complexity ） 算法的时间复杂度：在算法运行期间所花费的时间。 通常用渐进形式表示 比如，T(n)= 2 2 2 Ο(n ) 、Ω(n ) 或 Θ(n ) 空间复杂度 （Space Complexity） 算法的空间复杂度：在算法运行期间所需要的内存空间。 一般是指，除开容纳输入数据之外的附加空间（auxiliary space, or work space ）。 通常用渐进形式表示 比如，S(n)= 2 2 2 Ο(n ) 、Ω(n )或Θ(n ) W.D.Chen South China Normal University 4 1.4. 算法分析(Algorithm Analysis) 算法分析：对于算法的时间和空间复杂度进行定量 分析。 分析算法时间复杂度的基本步骤 算法时间复杂度的有关概念 分析、求解算法复杂度的基本方法 W.D.Chen South China Normal University 5 1.4.1. 分析时间复杂度的基本步骤 一、选取一种运算作为基本运算 二、表示出在算法运行期间基本运算执行的总频数 三、渐近时间复杂度（asymptotic time complexity ） W.D.Chen South China Normal University 6 渐近表示的记号—O Ο-记号 设f (n)和g(n)均是从自然数集到非负实数集上的函 数。如果存在常数c0和一个自然数n0 ，使得对于任 意的n≥n0 ，均有 f (n)≤cg(n), 则 f (n)=