[科普中国]-程序性能

概述

程序性能是指运行程序所需要的内存和时间的多少。有两种方法来确定一个程序的性能：一个是分析方法；另一个是实验方法。在性能分析(performance analysis)时，采用分析方法，而在性能测量(performance measurement)时，使用实验方法。1

应用程序的性能很大程度上依赖于所采用的算法，从这个意义上讲，算法是程序的灵魂。运行时间和占用空间是算法性能最关键的指标，可以考察这些指标的实际值，比如可利用计时工具来考察运行时间，又如操作系统中的相关工具可以查看占用空间。从效率观点看，高效的算法意味其执行过程消耗的机器资源较少，而计算机系统必要的构成是CPU和内存，那么肯定得要求算法的执行过程应尽量少占用处理机时间和内存。

不过，这些具体且“实际”的指标值却是不“实用”的性能指标，一方面，不同的计算机由于性能各异造成指标值不同；另一方面，这些指标值随着输入数据不同而相差较大．显然，可以在某些条件上给出具体的指标值，但这无法适用于所有情况。鉴于此，理论分析工具的呼唤是必然的，而如今此方面的研究已经成长为算法分析(Algorithm Analysis)这个专门的领域。

算法分析一般是理论上的，它可以在算法运行之前进行预判，也可以在算法运行之后进行总结改进，但算法分析代替不了实际的性能测试，必须在真正的计算机上利用实际的编译器得到可执行的代码运行，根据实测效果进行优化并重新给出更精准的分析，这样才能达到最佳的效果。

时间复杂度(Time complexity)，算法完全运行所需运算时间。

空间复杂度(Space complexity)，算法完全运行所需存储空间。

这两个指标衡量了算法的时空效率，为区分数据取值情况对性能分析带来的影响，可将时间复杂度和空间复杂度加上一定的限制：

最坏情况下的时间/空间复杂度，对于指定问题规模量，输入遍取所有可能情况下时问/空间复杂度的最大值。

最好情况下的时间/空间复杂度，对于指定问题规模量，输入遍取所有可能情况下时间/空间复杂度的最小值。

平均情况下的时间/空间复杂度，对于指定问题规模量，输入遍取所有可能情况下时间/空间复杂度的数学期望，通常假设输入数据满足等概率分布。2

算法空间复杂度空间复杂度(space complexity)是指一个算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句(运算)的多少。算法的时间复杂度通常用该算法执行的总语句(运算)的数量级决定。

就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它的所有语句执行频数之和。

研究的原因：

(1)如果一个程序要运行在一个多用户计算机系统中，那么需要指明该程序所需内存的大小。

(2)在任何一个计算机系统上运行程序，都需要知道是否有足够的内存可以用来运行该程序。

(3)一个问题可能有若干个解决方案，它们对内存的需求各不相同。比如，某个C++编译器仅需要1MB的空间，而另一个C++编译器可能需要4MB的空间，如果计算机内存少于4MB，那么只能选择第一个编译器。即使计算机有足够的内存．如果两个编译器作用相同，那么也宁愿使用较小的编泽器，以便把更多的内存留作他用。

(4)利用空间复杂度可以估算一个程序所能解决的问题最大可以是什么规模。1

时间复杂度算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。

一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与静态变量等所占的空间。可变空间需求包括局部作用域非静态变量所占用的空间、从堆空间中动态分配的空间与调用函数所需的系统栈空间等。

通常用算法设置的变量(数组)所占内存单元的数量级来定义该算法的空间复杂度。如果一个算法占的内存空间很大，在实际应用时该算法也是很难实现的。3

研究的原因：

1、有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。可以简单地指定时间上限为几千年．可是，如果程序因为数据问题而陷入死循环，可要为机时付出巨额资金。因此希望时间上限应该稍大于所期望的运行时间。

2、正在开发的程序可能需要一个令人满意的实时响应(realtime response)。例如，所有交互式程序都必须如此。一个文本编辑器(text editor)，光标上移一页或下移一页需要1min．就很难找到用户；一个电子制表软件(spreadsheet)，对一个单元重新计值需要几分钟，就没人乐意买账；一个数据库管理系统(database management system)，对一个关系进行排序时，用户可以有时间去喝两杯咖啡，就不可能有市场。为交互式应用所设计的程序都必须具有令人满意的实时响应。

3、如果一个问题有多种解决方案，那么具体采用哪一种方案，主要根据这些方案的性能差异。对于各种方案的时间和空间性能，采用加权测量方式进行评价。1