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

《《算法设计与分析》第2章》由会员分享，可在线阅读，更多相关《《算法设计与分析》第2章（65页珍藏版）》请在金锄头文库上搜索。

1、第2章 算法分析基础,2017/7/23,成都学院计算机系,-2-,2.1 算法复杂度 2.2 渐近表示法 2.3 递推关系,2017/7/23,成都学院计算机系,-3-,主要知识点,掌握好算法的评价标准;了解影响程序运行时间的因素;掌握算法的评价标准:时间复杂度和空间复杂度的概念;掌握渐近时间复杂度的几种表示方式;掌握常见时间复杂度渐近表示之间的关系.,2.1 算法复杂度,2017/7/23,成都学院计算机系,-5-,2.1.1 什么是好的算法,好的算法 一个好的算法应具有以下4个重要特性:正确性（correctness）：算法的执行结果应当满足预先规定的功能和性能要求。简明性（simpli

2、city）：算法应思路清晰、层次分明、容易理解、利于编码和调试。效率（efficiency）：算法应有效使用存储空间，并具有高的时间效率。最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。,2017/7/23,成都学院计算机系,-6-,程序健壮性 是指当输入不合法数据时，程序应能做适当处理而不至于引起严重后果。其含义是：当程序万一遇到意外时，能按某种预定方式做出适当处理。正确性和健壮性是相互补充的。,2017/7/23,成都学院计算机系,-7-,2.1.2 影响程序运行时间的因素,程序运行时间是指程序从开始到结束所需的时间。程序运行所需的时间依赖于计算机软、硬件系

3、统。在完全相同的计算机环境下，影响程序运行时间的因素主要有：程序所依赖的算法；问题规模和输入数据；计算机系统性能。,2017/7/23,成都学院计算机系,-8-,算法效率的度量分为事前估计和后期测试。后期测试主要通过在算法中的某些部位插装时间函数来测定算法完成某一功能所需的时间。事前估计主要是分析算法的复杂性，包括空间复杂度和时间复杂度。 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。,2017/7/23,成都学院计算机系,-9-,1）事前分析目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。如何给出反映算法执行特性的描述？

4、 最直接方法：统计算法中各种运算的执行情况，包括：运用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间等。 算法的执行时间=Fi*ti,2017/7/23,成都学院计算机系,-10-,频率计数 例： xx+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)： xx+y执行了1次 (b)： xx+y执行了n次 (c)： xx+y执行了n2次 定义： 频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。,2017/7/23

5、,成都学院计算机系,-11-,一条语句在整个程序运行时实际执行时间= 频率计数 * 每执行一次该语句所需的时间 如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。,2017/7/23,成都学院计算机系,-12-,数量级语句的数量级：语句的执行频率 例：1，n ，n2算法的数量级：算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有n， n2 ， n3数 量级。 若n=

6、10，则可能的执行时间将分别是10，100，1000个单 位时间与环境因素无关。,2017/7/23,成都学院计算机系,-13-,计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n)注：最高次项与函数整体的关系空间特性分析（略）,2017/7/23,成都学院计算机系,-14-,2）事后测试目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图,2017/7/23,成都学院计算机系,-15-,2.1.3 算法的时间复杂度,抽象机模

7、型 设抽象机提供由m个基本运算（也可称为语句）组成的运算集O = O1, O2, , Om，每个运算都是基本的，它们的执行时间是有限常量。同时设执行第i个运算Oi所需的时间是i，1im。 一个算法对于给定的抽象机上的一次执行过程，表现为执行一个基本运算的序列。,2017/7/23,成都学院计算机系,-16-,时间复杂度一个算法的时间复杂度（time complexity）是指算法运行所需的时间。设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n, I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为i，1im，i也是n和

8、I的函数，记做i(n, I)。那么，算法A在输入为I时的运行时间是：,2017/7/23,成都学院计算机系,-17-,称为算法的时间复杂度。 其中，输入数据I是问题的实例，n是问题的规模。 要全面分析一个算法，需要考虑算法在最坏情况下的时间代价，在最好情况下的时间代价以及在平均情况下的时间代价。,2017/7/23,成都学院计算机系,-18-,最好、最坏和平均时间复杂度最好时间复杂度B(n)最坏时间复杂度W(n)平均时间复杂度A(n) Dn是规模为n的所有合法输入的集合，I和I*分别为Dn中算法运行最好和最坏情况的输入数据，P(I)是输入数据I在具体应用中被使用的概率。,2017/7/23,成

9、都学院计算机系,-19-,2.1.4 使用程序步分析算法,一个程序步（program step）是指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。,2017/7/23,成都学院计算机系,-20-,【程序2-1】 求数组元素累加之和的迭代程序float Sum(float list, const int n) float tempsum=0.0; count +; /针对赋值语句 for (int i=0; in; i+ ) count +; /针对for循环语句 tempsum+ =listi; count +; /针对赋值语句 count +; /针对for的最

10、后一次执行 count +; /针对return语句 return tempsum;,2017/7/23,成都学院计算机系,-21-,【程序2-2】求数组元素累加之和的递归程序float RSum(float list, const int n) count +; /针对 if 条件 if (n) count+; /针对 RSum 调用和return语句 return RSum(list, n-1)+listn-1; count+; /针对return语句 return 0;,2017/7/23,成都学院计算机系,-22-,设RSum（list,n）的程序步为T(n),T(n)=2+T(n-1

11、)=2+2+T(n-2) =2*3+T(n-3) =2*n+T(0) =2*n+2,2017/7/23,成都学院计算机系,-23-,2.1.5 算法的空间复杂度,空间复杂度（space complexity）是指算法运行所需的存储空间。程序运行所需的存储空间包括以下两部分：固定空间需求（fixed space requirement） 这部分空间与所处理数据的大小和个数无关，也就是说，与问题实例的特征无关。 可变空间需求（variable space requirement） 这部分空间大小与算法在某次执行中处理的特定数据的规模有关。,2.2 渐近表示法,2017/7/23,成都学院计算机系,

12、-25-,算法渐近复杂性概念,T(n) , 当 n 时有: (T(n) - t(n) )/ T(n) 0 t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上，t(n)是T(n)的渐近表达式，实质是T(n)略去低阶项留下的主项。它比T(n) 简单。,2017/7/23,成都学院计算机系,-26-,例T(n)=3N2+4NlogN+7时,求它的一个渐近表达式 t(n)的一个答案是3N2,2017/7/23,成都学院计算机系,-27-,记：算法的计算时间为f(n) 数量级限界函数为g(n)其中， n是输入或输出规模的某种测度。 f(n)表示算法的“实际”执行时间与机器及语言有关。 g(n)

13、是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、与机器及语言无关的函数。 以下给出算法执行时间：上界（）、下界（）、“平均”（ ）的定义。,2017/7/23,成都学院计算机系,-28-,2.2.1 渐近上界记号(O),如果存在两个正常数c和n0，对于所有的nn0，有 |f(n)| c|g(n)| 则记作f(n) = (g(n) 称为大O记号（big Oh notation）。使用大O记号及后面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度（asymptotic complexity）,2017/7/23,成都学院计算机系,-29-,例 1 f(n) = 2n + 3 是否等于O(n)当n3时，2n+33n 可选c = 3，n0 = 3。 对于nn0，f(n) = 2n + 33n。所以，f(n) = O(n)，即2n + 3O(n)。,2017/7/23,成都学院计算机系,-30-,例2 f(n) = 10n2 + 4n + 2 的O表示形式.对于n2时,10n2 + 4n + 210n2 + 5n 并且当n5时，5nn2 因此，可选c = 11, n0 = 5；对于nn0，f(n) = 10n2 + 4n + 211n2所以f(n) = O(n2)。,