程序的性能分析.pdf

学习程序算法的一个总要目标就是学会判断程序性能的优劣。 当然判 断的标准有很多，至少包括如下几点： 1.程序是否符合任务的规范说明。 2. 程序是否正确。 3. 是否有配套文档，说明程序的用法和原理。 4. 程序是否根据逻辑关系分解成能有效执行的函数。 5. 程序代码是否易读。 以上判据至关重要，对构建大规模程序系统，显得更为关键。然而若 要 指出上述标准却并非易事。除了上述一般性判据之外，以下两条判 据更 加具体。 6. 程序是否能够高效使用主存和辅存。 7. 程序的运行时间是否令人满意 最后这两条可以分两方面来讨论：第一方面的性能估计与机器无关， 来 推断程序的空间代价和时间代价， 称为性能分析；第二方面称为性 能度 量，即获取程序在真实环境的实际运行时间。 定义 空间复杂度是程序运行所需的存储空间；时间复杂度是程序的 运行 时间。 一. 空间复杂度 程序运行所需空间包括两部分： 1.定长空间需求：即与程序输入、输出无关的空间。 第1页 2. 变长空间需求：即与求解的问题实例相关的结构化变量所占的空间 大 小。如果是递归程序，还应加上递归时所需工作空间的大小。 任何程序所需的空间大小就是上述两块空间的总和。 但分析一个程序 的 空间复杂度，通常仅仅考察变长空间需求。 看下面例子： 代码1: float abc(float a, float b,float c) retur n a+b+b*c+(a+b-c)/(a+b)+4.00; 函数abc 的输入是三个简单变量，输出返回一个简单变量。根据以 上分 类，这个函数只有定长空间需求，因此空间复杂度为 0. 代码2 : float sum(float list[], i nt n) float tempsum =0; int i; for(i=0;i n ;i++) tempsum+=list[i]; retur n tempsum; 代码2 的输出只有一个简单变量，但输入比上例增加了一个数组，这 里 变长空间需求依赖于数组参量是如何传入函数的。 不同语言的处理 各不相同，对于Pascal 语言，数组参量是按值传递的，也就是说这 个函 数在执行时，整个数组被复制到函数的临时存储空间。 这样空间 第2页 复杂度就为n，n 是数组长度。c 语言的参数传递方法虽然也是传值 调 用，但c 只传递数组一个元素的首地址，并不复制数组，因而空间 复杂 度为0. 代码3 : float sum(float list[], i nt n) if(n) retur n sum(list, n-1)+list[ n-1]; else retur n 0; 代码3 也是增加了一个数组，不过这个球和程序是递归程序，编译器 要 为每次递归调用保存参量、局部变量、返回地址。一次递归所需的 空间 就是两个参量加上返回地址的字节数。 比较求和和程序的循环实现和递归实现，前者无变长空间需求，而后 者 的开销要大许多。 二. 时间复杂度 程序的时间开销是编译时间和运行(执行)时间的总和。编译时间与 定长 空间需求类似，同样与实例特征无关，而且，程序经检验确定其 正确性 之后，编译结果可不断执行。所以时间复杂度仅考虑程序的执 行时间。 比较简单的方法，是统计执行时所需各种操作的次数。这种 方法的计数 结果与机器无关，但首先要把程序分成独立的程序步。 这里要注意：a=2 ;是一个程序步，a=2*b-a+5/4*6; 也是一个程序 步。虽 然执行时间不同，但都被看作一步。 有时候，执行同样的功能，递归程序的程序步比相应循环程序步少， 第3页 初看令人惊奇，但不要忘记，程序步的计数告诉我们程序以多少个步 骤 执行，并没有告诉我们每一步的执行时间。事实上递归程序的执行 一般 而言要比循环程序慢，所以花的时间往往要比循环程序多一些。 还有要注意的是，只有在程序的相应特征 (n,m,p,q, …)选定后，才 可以 定义什么是程序步。程序步是与特征无关的计算单位。 所以，