3.7 技术解惑

3.7.1 衡量算法的标准是什么

算法的优劣有如下5个标准。

· 确定性。算法的每一种运算必须有确定的意义,这种运算应执行何种动作应无二义性,目的明确。

· 可行性。要求算法中待实现的运算都是可行的,即至少在原理上能由人用纸和笔在有限的时间内完成。

· 输入。一个算法有零个或多个输入,在算法运算开始之前给出算法所需数据的初值,这些输入来自特定的对象集合。

· 输出。输出是算法运算的结果,一个算法会产生一个或多个输出,输出同输入具有某种特定关系。

· 有穷性。一个算法总是在执行有穷步的运算后终止,即该算法是有终点的。

通常有如下两种衡量算法效率的方法。

· 事后统计法。该方法的缺点是必须在计算机上实际运行程序,容易被其他因素掩盖算法本质。

· 事前分析估算法。该方法的优点是可以预先比较各种算法,以便均衡利弊从中选优。

与算法执行时间相关的因素如下。

· 算法所用“策略”。

· 算法所解问题的“规模”。

· 编程所用“语言”。

· “编译”的质量。

· 执行算法的计算机的“速度”。

在上述因素中,后3个因素受计算机硬件和软件的制约,因为是“估算”,所以只需要考虑前两个因素即可。

事后统计容易陷入盲目境地,例如,当程序执行很长时间仍未结束时,不易判别是程序错了还是确实需要那么长时间。

算法的“运行工作量”通常随问题规模的增长而增长,所以应该用“增长趋势”来作为比较不同算法的优劣的准则。假如,随着问题规模n的增长,算法执行时间的增长率与f(n)的增长率相同,可记作T(n)=O(f(n)),称T(n)为算法的(渐近)时间复杂度。

究竟如何估算算法的时间复杂度呢?任何一个算法都是由一个“控制结构”和若干“原操作”组成的,所以可以将算法的执行时间看作:所有原操作的执行时间之和∑(原操作(i)的执行次数×原操作(i)的执行时间)。

算法的执行时间与所有原操作的执行次数之和成正比。对于所研究的问题来说,从算法中选取一种基本操作的原操作,以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。以这种衡量效率的办法得出的不是时间量,而是一种对增长趋势的量度。它与软硬件环境无关,只暴露算法本身执行效率的优劣。