《程序的性能分析》word版

《《程序的性能分析》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、学习程序算法的一个总要目标就是学会判断程序性能的优劣。当然判断的标准有很多，至少包括如下几点：1.程序是否符合任务的规范说明。2.程序是否正确。3.是否有配套文档，说明程序的用法和原理。4.程序是否根据逻辑关系分解成能有效执行的函数。5.程序代码是否易读。以上判据至关重要，对构建大规模程序系统，显得更为关键。然而若要指出上述标准却并非易事。除了上述一般性判据之外，以下两条判据更加具体。6.程序是否能够高效使用主存和辅存。7.程序的运行时间是否令人满意最后这两条可以分两方面来讨论：第一方面的性能估计与机器无关，来推断程序的空间代价和时间代价，称为性能分析；第二方面称为性能

2、度量，即获取程序在真实环境的实际运行时间。定义空间复杂度是程序运行所需的存储空间；时间复杂度是程序的运行时间。一．空间复杂度程序运行所需空间包括两部分：1.定长空间需求：即与程序输入、输出无关的空间。2.变长空间需求：即与求解的问题实例相关的结构化变量所占的空间大小。如果是递归程序，还应加上递归时所需工作空间的大小。任何程序所需的空间大小就是上述两块空间的总和。但分析一个程序的空间复杂度，通常仅仅考察变长空间需求。看下面例子：代码1：floatabc(floata,floatb,floatc){returna+b+b*c+(a+b-c)/(a+b)+4.00;}函数ab

3、c的输入是三个简单变量，输出返回一个简单变量。根据以上分类，这个函数只有定长空间需求，因此空间复杂度为0.代码2：floatsum(floatlist[],intn){floattempsum=0;inti;for(i=0;i

4、c语言的参数传递方法虽然也是传值调用，但c只传递数组一个元素的首地址，并不复制数组，因而空间复杂度为0.代码3：floatsum(floatlist[],intn){if(n)returnsum(list,n-1)+list[n-1];elsereturn0;}代码3也是增加了一个数组，不过这个球和程序是递归程序，编译器要为每次递归调用保存参量、局部变量、返回地址。一次递归所需的空间就是两个参量加上返回地址的字节数。比较求和和程序的循环实现和递归实现，前者无变长空间需求，而后者的开销要大许多。二．时间复杂度程序的时间开销是编译时间和运行（执行）时间的总和。编译时间与定长

5、空间需求类似，同样与实例特征无关，而且，程序经检验确定其正确性之后，编译结果可不断执行。所以时间复杂度仅考虑程序的执行时间。比较简单的方法，是统计执行时所需各种操作的次数。这种方法的计数结果与机器无关，但首先要把程序分成独立的程序步。这里要注意：a=2；是一个程序步，a=2*b-a+5/4*6;也是一个程序步。虽然执行时间不同，但都被看作一步。有时候，执行同样的功能，递归程序的程序步比相应循环程序步少，初看令人惊奇，但不要忘记，程序步的计数告诉我们程序以多少个步骤执行，并没有告诉我们每一步的执行时间。事实上递归程序的执行一般而言要比循环程序慢，所以花的时间往往要比循环程

6、序多一些。还有要注意的是，只有在程序的相应特征（n,m,p,q,r...）选定后，才可以定义什么是程序步。程序步是与特征无关的计算单位。所以，10次加法可以是一个程序步，1000次乘法也可以是一个程序步。但n次加法却不可以是一个程序步，因为它的大小已经与相应特征有关了。二．渐进记号O由于程序步不能表示程序运行每一步的时间，因此即使用精确的程序步值做比较，结果也是不准确的。只有在程序步数目相差很大时，例如3n+3和100n+10相比才有意义。对于多数情形，能够给出如下论断就可以了，如，其中和是非负常量。原因是当n充分大的时候，上式中前者会明显比后者运行的更快，而n比较小的

7、时候，快慢是不确定的（取决于和的取值）。但是不论取何值，总存在一个n值，之后，复杂度为的程序总没有复杂度为的程序运行的快，这个n值称为失衡点（breakevenpoint）。一旦知道了一定存在一个失衡点，然后形式地得到程序的复杂度，，我们所需的信息已经足够了。不再需要刻意找出精确值。我们把这种存在失衡点的复杂度关系中所能达到的复杂度记作O。例如3n+2=O(n),,,特别的,我们用O(1)表示恒定的时间复杂度。如果一个算法的时间复杂度是O(㏒n)那么对充分大的n，该算法的复杂度比O(n)的算法运行的更快。