算法评价的几个方面及其重要性

对于数据的任何一种运算，如果数据的存储结构不同，则其算法描述一般也是不相同的，即使在存储结构相同的情况下，由于可以采用不同的求解策略，所以往往也可以有许多不同的算法。对算法进行评价，既可以解决在同一问题的不同算法中选择出较为合适的一种算法，也可以知道如何对现有的算法进行改进，从而设计出更好的算法。评价一个算法的准则很多，例如算法是否正确，是否易于理解、易于编码、易于测试以及算法是否节省时间和空间等。那么如何选择一个好的算法呢？

通常设计一个好的算法应考虑以下几个方面：

❶ 正确性

正确性是设计和评价一个算法的首要条件，如果一个算法不正确，其他方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的运行时间内得出正确的结果。通过对数据输入的所有可能的分析和上机调试，可以证明此算法是否正确。当然，要从理论上证明一个算法是否正确，并不是一件容易的事。

“正确”的含义在通常的用法中有很大的差别，但大体可分为以下四个层次：

① 程序不含语法错误；

② 程序对于几组输入数据能够得出满足规格说明要求的结果；

③ 程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；

④ 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

显然，达到第④层意义下的正确是极为困难的，因为所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。对于大型软件需要进行专业的测试，而一般情况下，通常以第③层意义下的正确作为衡量一个程序是否正确的标准。

❷ 运行时间(www.xing528.com)

运行时间是指一个算法在计算机上运算所花费的时间，它大致等于计算机执行一种简单操作（如赋值操作、转向操作和比较操作，等等）所需要的时间与算法中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身的软硬件环境决定的，与算法无关，所以这里只讨论影响运行时间的另一因素——算法中进行简单操作的次数。

显然，在一个算法中，进行简单操作的次数越少，其运行时间也就相对越短；进行简单操作的次数越多，其运行时间也就相对越长。因此，通常把算法中包含简单操作的次数叫做算法的时间复杂性，它是算法运行时间的一个相对量度。

❸ 占用的存储空间

一个算法在计算机存储器上所占用的存储空间包括算法的输入、输出数据所占用的存储空间，存储算法本身所占用的存储空间和算法运行过程中临时占用的存储空间这三个方面。算法的输入、输出数据所占用的存储空间是由要解决的问题所决定的，它不随算法的不同而改变。存储算法本身所占用的存储空间与算法的长短成正比，所以要压缩这方面的存储空间，就必须编写较短的算法。算法运行过程中临时占用的存储空间随算法的不同而不同，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，所以我们称这种算法是“就地”进行的，是节省存储空间的算法；有的算法需要占用的临时工作单元数和问题的规模n成正比，当n较大时，将占用较多的存储单元，从而浪费存储空间。

分析一个算法所占用的存储空间要从各方面综合考虑，如对于递归算法来说，其一般都比较简短，所以算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，则一般比较长，算法本身所占用的存储空间较长，但运行时将占用较少的存储单元。

算法在运行过程中所占用的存储空间的大小被称为算法的空间复杂性。算法的空间复杂性比较容易计算，它包括局部变量（即在本算法中说明的变量）所占用的存储空间和系统为了实现递归（如果是递归算法）所使用的堆栈这两个部分。算法的空间复杂性一般也以数量级的形式给出。

❹ 简单性

一般来说，最简单和最直接的算法都不是最有效的算法，但算法的简单性可以使得正确性的证明比较容易，而且便于编写、修改、阅读和调试，所以简单性还是应当强调和不容忽视的。但是对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。

以上讨论了如何从四个方面来评价一个算法的问题。这里还需要指出，除了算法的正确性之外，其余三个方面往往是相互矛盾的。当追求较短的运行时间时，可能会带来占用较多的存储空间和较繁的算法；当追求占用较少的存储空间时，可能会带来较长的运行时间和较繁的算法；当追求算法的简单性时，可能会带来较长的运行时间和占用较多的存储空间。因此，在设计一个算法时，要从这三个方面来综合考虑，同时还要考虑到算法的使用频率、算法的结构化和易读性以及所使用机器的软硬件环境等因素，这样才能设计出比较好的算法。