《算法设计与分析》第2章.pptVIP

成都学院计算机系 第2章 算法分析基础 主要知识点 掌握好算法的评价标准; 了解影响程序运行时间的因素; 掌握算法的评价标准:时间复杂度和空间复杂度的概念; 掌握渐近时间复杂度的几种表示方式; 掌握常见时间复杂度渐近表示之间的关系. 2.1 算法复杂度 2.1.1 什么是好的算法 好的算法 一个好的算法应具有以下4个重要特性: 正确性（correctness）：算法的执行结果应当满足预先规定的功能和性能要求。 简明性（simplicity）：算法应思路清晰、层次分明、容易理解、利于编码和调试。 效率（efficiency）：算法应有效使用存储空间，并具有高的时间效率。 最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。 2.1.2 影响程序运行时间的因素 算法效率的度量分为事前估计和后期测试。 后期测试主要通过在算法中的某些部位插装时间函数来测定算法完成某一功能所需的时间。 事前估计主要是分析算法的复杂性，包括空间复杂度和时间复杂度。 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。 1）事前分析 目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。 如何给出反映算法执行特性的描述？ 最直接方法：统计算法中各种运算的执行情况，包括： 运用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。 算法的执行时间=∑Fi*ti 频率计数 例： x←x+y for i ←1 to n do for i ←1 to n do x ← x + y for j ←1 to n do repeat x ← x +y repeat repeat (a) (b) (c) 分析： (a)： x←x+y执行了1次 (b)： x←x+y执行了n次 (c)： x←x+y执行了n2次 定义： 频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。 一条语句在整个程序运行时实际执行时间= 频率计数 * 每执行一次该语句所需的时间 如何刻画算法执行特性的形式描述 实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。 在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。 数量级 语句的数量级：语句的执行频率 例：1，n ，n2 算法的数量级：算法所包含的所有语句的执 行频率之和。 算法的数量级从本质上反映了一个算法的执行特性。 例：假如求解同一个问题的三个算法分别具有n， n2 ， n3数 量级。 若n=10，则可能的执行时间将分别是10，100，1000个单 位时间——与环境因素无关。 计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n) 注：最高次项与函数整体的关系 空间特性分析（略） 2）事后测试 目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。 分析手段：作时、空性能分布图 2.1.3 算法的时间复杂度 时间复杂度 一个算法的时间复杂度（time complexity）是指算法运行所需的时间。 设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n, I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为?i，1≤i≤m，?i也是n和I的函数，记做?i(n, I)。那么，算法A在输入为I时的运行时间是： 2.1.4 使用程序步分析算法 2.1.5 算法的空间复杂度 2.2 渐近表示法 算法渐近复杂性概念 T(n) ?? , 当 n?? 时有: (T(n) - t(n) )/ T(n) ?0 t(n)是T(n