3.1.1. 引言¶

就求解某个问题的两种算法而言，如何在效率上加以比较？ 我们可以把两种算法都实现为计算机程序， 然后在适当范围的输入上运行它们， 测量每个程序使用了多少相关资源。 这种做法常常不能令人满意，原因有四。 第一，你充其量只想保留其中一个算法， 却要为两个算法的编程和测试付出努力。 第二，在做实验比较时，总有可能其中一个程序比另一个 "写得更好"，因而底层算法的相对优劣并没有真正由其 实现体现出来。 当程序员对涉及的算法有所偏爱时，这种情况很容易发生。 第三，实验测试用例的选择可能不公平地偏向某个算法。 第四，你可能会发现，即便是两个算法中较好的那个， 也不在你的资源预算之内。 那样的话，你就得用实现了新算法的又一个程序， 把整个过程从头再来一遍。 可是，你怎么知道是否存在能满足资源预算的算法？ 也许这个问题本身就太难，任何实现都无法控制在 预算之内。

使用渐近分析常常可以避免这些问题。 渐近分析度量的是当输入规模变大时，算法（或其作为程序的 实现）的效率。 它实际上是一种估计技术，对于两个程序的相对优劣 给不出什么结论，比如一个程序只是总比另一个 "稍快一点"的情形。 然而，事实证明，对于必须判断某个特定算法是否值得 考虑实现的计算机科学家来说，渐近分析是有用的。

程序最关键的资源通常是其运行时间。 不过，你不能只关注运行时间， 还必须关心其他因素，比如运行程序所需的空间 （主存和磁盘空间都在内）。 典型做法是：分析 算法 （或算法以程序形式实例化后） 所需的 时间 ，以及 数据结构 所需的 空间 。

影响程序运行时间的因素很多。 有些因素与程序编译和运行所处的环境有关， 比如计算机的 CPU、总线和外设硬件的速度。 与其他用户争夺计算机（或网络）的资源， 可能让程序慢得像爬行一样。 程序设计语言以及特定编译器所生成代码的质量， 也会有显著影响。 把算法转换为程序的程序员其"编码效率"如何， 同样可能带来巨大影响。

如果你要让程序在特定计算机上于时间和空间约束之内 正常工作，所有这些因素都可能相关。 然而，这些因素没有一个涉及两种算法或数据结构之间的 差异。 公平地说，如果想比较由求解同一问题的两个算法分别 得到的两个程序，就应当用同一编译器编译它们， 并在相同条件下在同一台计算机上运行。 在为每个程序付出的编程投入上，还应尽量花费同等的 心力，使两个实现"同等高效"。 在这个意义上，前面提到的所有因素都应当从比较中 抵消掉，因为它们对两种算法的影响是同等的。

如果你真正想理解算法的运行时间， 那么比起机器速度、程序设计语言、编译器等因素， 还有一些更合适的考虑因素。 理想情况下，我们会在标准的基准测试条件下度量 算法的运行时间。 然而，除了在某一台计算机上运行算法的实现之外， 我们没有可靠计算运行时间的办法。 唯一的替代方案，就是用某种别的度量来代替运行时间。

3.1.2. 基本操作与输入规模¶

在估计算法性能时，首要考虑的是：为处理一定规模的输入， 算法需要执行多少次 基本操作 。 "基本操作"和"规模"这两个说法都相当含糊， 取决于被分析的算法。 规模常常是指所处理输入的数目。 例如，比较排序算法时，问题规模通常用待排序记录的数目 来度量。 基本操作必须具有这样的性质：其完成所需的时间不依赖于 操作数的具体取值。 对两个整型变量做加法或比较， 就是大多数程序设计语言中基本操作的例子。 对一个含 \(n\) 个整数的数组求和则不是， 因为代价取决于 \(n\) 的值（即输入的规模）。

3.1.3. 增长率¶

算法的 增长率 是指：当算法输入的 规模增大时，算法代价增长的速度。 下图给出了六条方程的图象， 每条方程都想描述某个特定程序或算法的运行时间。 图中展示了能够代表典型算法的多种增长率。

标记为 \(10n\) 和 \(20n\) 的两条方程画出来 是直线。 增长率为 \(cn\) （其中 \(c\) 为任意正常数） 常被称为 线性增长率 或 线性运行时间。 这意味着随着 \(n\) 的值增大， 算法的运行时间按同样的比例增长。 当 \(n\) 的值翻倍时，运行时间大致也翻倍。 运行时间方程的最高次项含有 \(n^2\) 因子的算法， 称为具有 二次增长率 。 图中标记为 \(2n^2\) 的线表示二次增长率。 标记为 \(2^n\) 的线表示的是 指数增长率 。 这个名称源于 \(n\) 出现在指数位置。 标记为 \(n!\) 的线同样按指数级增长。

正如您从图中所见，运行时间成本为 \(\mathbf{T}(n) = 10n\) 的算法与成本为 \(\mathbf{T}(n) = 2n^2\) 的算法之间的差异随着 \(n\) 的增长而变得巨大。对于 \(n > 5\) ，运行时间为 \(\mathbf{T}(n) = 2n^2\) 的算法已经慢得多。尽管 \(10n\) 的常数因子大于 \(2n^2\) 。比较标记为 \(20n\) 和 \(2n^2\) 的两条曲线表明，改变其中一个方程的常数因子只会移动两条曲线相交的点。对于 \(n>10\) ，成本为 \(\mathbf{T}(n) = 2n^2\) 的算法比成本为 \(\mathbf{T}(n) = 20n\) 的算法更慢。该图还显示，方程 \(\mathbf{T}(n) = 5 n \log n\) 的增长速度略快于 \(\mathbf{T}(n) = 10 n\) 和 \(\mathbf{T}(n) = 20 n\) ，但远不及方程 \(\mathbf{T}(n) = 2n^2\) 的增长速度快。对于常数， \(a, b > 1, n^a\) 的增长速度快于 \(\log^b n\) 或 \(\log n^b\) 。最后，即使对于适中的 \(n\) 值，成本为 \(\mathbf{T}(n) = 2^n\) 或 \(\mathbf{T}(n) = n!\) 的算法也昂贵得令人无法接受。请注意，对于常数， \(a, b \geq 1, a^n\) 的增长速度快于 \(n^b\) 。

从下表中，我们可以进一步洞察各种算法相对增长率的高低。 表中列出了典型算法中出现的大多数增长率， 以及一些有代表性的输入规模。 我们再一次看到，增长率对算法消耗的资源有着巨大的影响。