3.7 技术解惑

3.7.1 衡量算法的标准是什么

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

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

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

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

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

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

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

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

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

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

· 算法所用“策略”。

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

· 编程所用“语言”。

· “编译”的质量。

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

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

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

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

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

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