1.6 算法分析和评价

算法设计的优劣决定着软件系统的性能，算法分析（Analying Algorithm）的任务是利用数学工具讨论设计出的每个具体算法的复杂度。对算法进行分析一方面能深刻地理解问题的本质以及找出可能求解的技术；另一方面可以探讨某种具体算法适用于哪类问题，或某类问题应该采用哪种算法。

对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3 条主要标准是：

（1）算法实现所耗费的时间。

（2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间。

（3）算法应易于理解、易于编码、易于调试等。

早期由于硬件资源的匮乏和配制低劣，算法对前两个因素特别重要，不惜忽视后一条标准。而当今随着软件规模的不断增大，难度不断提高，应用范围越来越广泛，稳定性要求越来越高，这就更加要求注重算法易于理解、易于编码、易于调试的标准，当然这是要能得到硬件环境支持的。

对算法可维护方面的评价，不易定量度量，软件工程课程中有这方面的介绍。这里只介绍算法运行效率的评价方法。

1.6.1 算法的时间复杂度

1.和算法执行时间相关的因素

（1）问题中数据存储的数据结构。

（2）算法采用的数据模型。

（3）算法设计的策略。

（4）问题的规模。

（5）实现算法的程序语言。

（6）编译算法产生的机器代码的质量。

（7）计算机执行指令的速度。

2.算法时间效率的衡量方法

通常有两种衡量算法时间效率的方法。

1）事后分析法

一说到分析算法的时间效率，容易想到的是先将算法用程序设计语言实现，然后度量程序的运行时间，这种度量方法称为事后分析法。它的缺点是：

（1）必须先用程序设计语言实现算法，并执行算法才能进行判断算法的分析，这与算法分析的目的是违背的。

（2）不同的算法在相同环境下进行分析，工作效率太低。

（3）若不同算法运行环境有差异，其他因素（如硬件、软件环境）可能掩盖算法本质上的差异。

所以，一般很少采用事后分析法去对算法进行分析，除非是一些对响应速度要求特别高的自动控制算法或非常复杂不易分析的算法。

2）事前分析估算法

其实，一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数n来表示），或者说，算法的时间效率是问题规模的函数。例如，随着问题规模n的增长，算法执行的时间增长率和函数f（n）的增长率相同，可记作：

T（n）=O（f（n））

称T（n）为算法的渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。O是数量级的符号。

3.时间复杂度估算

一个程序的时间复杂度（Time Complexity）是指程序运行从开始到结束所需要的时间。一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T（n）。

许多时候要精确地计算T(n)是比较困难的，我们引入渐进时间复杂度在数量级上估计一个算法的执行时间，也能够达到分析算法的目的。

定义（大Ο记号）：如果存在两个正常数c和n ₀ ，使得对所有的n，n ≥ n ₀ ，有：

f(n)≤cg(n)

则有：

f(n)＝Ο(g(n))

时间复杂度：在算法分析中，算法整个运行过程所耗费的时间。具体计算如下：

（1）每个赋值语句或读/写语句的运行时间通常是Ο（1）。但有例外情况，如赋值语句的右部表达式可能出现函数调用，这时就要考虑计算函数值所耗费的时间。

（2）顺序语句的运行时间由线性规则决定，即为该序列中耗费时间最多的语句的运行时间。

（3）语句if的运行时间为条件语句测试时间［通常取O (1)］加上分支语句的运行时间；语句if-else-if的运行时间为条件测试时间加上分支语句的运行时间；当有多个分支时，以耗费时间最多的一个分支为准。

（4）循环语句的运行时间是n次重复执行循环体所耗费时间的总和。

（5）通常用Ο(1)表示常数计算时间。常见的渐进时间复杂度有：

Ο(1)＜Ο(log ₂ n)＜Ο(n)＜Ο(nlog ₂ n)＜Ο(n ² )＜Ο(n ³ )＜Ο(2 ⁿ )

随着问题规模n的增大，不同阶的时间复杂度增长快慢不一，如图1.8所示，因此，应尽可能选用多项式阶算法，而避免使用指数阶的算法。

假如一个程序的实际执行时间为T(n)＝2.7n ³ +3.8n ² +5.3。则T(n)＝O(n ³ )。

【例1.5】求两个 n 阶方阵的乘积C=A×B。

算法中所有语句的执行次数之和是矩阵阶数n的函数：T(n)=3n ³ +5n ² +4n+2。

当n趋于无穷大时，把时间复杂度的量级（阶）称为算法的时间复杂度：T(n)=O(n ³ )。

1.6.2 算法的空间复杂度

算法的存储量包括：

（1）输入数据所占的空间；

（2）算法（程序）本身所占的空间；

（3）辅助变量所占的空间。

其中，输入数据所占空间只取决于问题的本身，和算法无关。算法本身所占空间虽与算法无关，但一般其大小是相对固定的。所以，研究算法的空间效率，只须分析出输入数据和算法本身之外的辅助空间。若所需要辅助空间相对于输入数据量来说是常数，则称此算法为原地工作，否则，应当是输入数据规模的某个函数。

算法的空间复杂度是指算法在执行过程中所占辅助存储空间的大小（也有本书定义为所占全部存储空间的大小），用S（n）表示。S为英文单词space的第一个字母。与算法的时间复杂度相同，算法的空间复杂度S（n）也可以表示为S（n）=Ο(g(n))，表示随着问题规模n的增大，算法运行所需要存储量的增长与g（n）的增长率相同。 /u9EbgheuBE9jFANVdcm977UKu2WefzJ8JSNt7xTtwV+ihk43QGIkqks/JDevRzp