1.2 作为一种技术的算法

- · -

假设计算机无限快，并且计算机存储器是免费的，那么你还有任何理由来研究算法吗?如果你没有别的理由，就是仍然希望证明你的解决方案能够终止并给出正确的结果的话，那么答案就是“是的”。

如果计算机无限快，那么对于某一个问题来说，任何一个可以解决它的正确方法都是可以的。你很可能希望自己的实现能够符合良好的软件工程实践要求(亦即，具有良好的设计和文档说明)，但往往会采用最容易实现的方法。当然，计算机可以做得很快，但还不能是无限快。存储器可以做到很便宜，但不会是免费的。因此，计算时间是一种有限的资源，存储空间也是一种有限的资源。这些有限的资源必须被有效地使用，那些时间和空间上有效的算法就有助于做到这一点。

效率

解决同一问题的各种不同算法的效率常常相差很大。这种效率上差距的影响往往比硬件和 软件方面的差距还要来得大。

例如，在第 2 章中，我们将介绍两个排序算法。第一个称为插入排序算法，对 $n$ 个数据项进行排序的时间大约等于 $c_1n^2$,其中 $c_1$ 是一个不依赖于 $n$ 的常量。亦即，该算法所需的时间大致正比于 $n_2$。第二个是合并排序算法，它排序 $n$ 个数据项所需的时间大约是 $c_2n{\rm lg}n$，其中 ${\rm lg}n$ 表示 ${\rm log}_2n$, $c_2$ 是另一个同样也不依赖于 n 的常量。插入排序算法与合并排序算法相比，通常有着更小的常量因子，即 $c_1<c_2$。 后面我们还将看到，与对输人规模 $n$ 的依赖相比，常量因子对运行时间的影响要小得多。合并排序算法的运行时间中有个因子 ${\rm lg}n$，而插入排序算法的运行时间中有个因子 $n$，它要比前者大得多了。尽管对于较小的输人规模来说，插入排序要比合并排序更快些，但是，一旦输人规模 $n$ 变得足够大了以后，合并排序的 ${\rm lg}n$与 $n$ 相比的优势就远远不止是弥补两者之间常量因子上的差距了。无论 $c_1$ 比 $c_2$ 小多少，总会有一个转折点，过了这个点以后，合并排序就会比插入排序运行得更快了。

我们来看一个具体的例子。让一台更快的、运行插入排序的计算机(计算机 A)与一台较慢的、运行合并排序的计算机(计算机 B)进行比较。两者都要对一个大小为一百万个数的数组进行排序。假设计算机 A 每秒能执行 10 亿条指令，而计算机 B 每秒只能执行一千万条指令。因此，在计算能力方面，计算机 A 要比计算机 B 快 100 倍。为了使这一差距更为明显，假设让世界上最能干的程序员采用机器语言，来为计算机 A 编写插入排序算法的代码，所得到的代码需要 $2n^2$ 条指令来排序 n 个数(此处，$c_1=2$)。 另一方面，让一位平均熟练水平的程序员，采用某种具有低效编译器的高级语言来为计算机 B 编写合并排序算法的代码，所得到的代码有 $50n{\rm lg}n$ 条指令(这里 $c2=50$)。为了排序一百万个数，计算机 A 花的时间为:

$$\frac{2 \bullet (10^6)^2{\rm 条指令}}{10^9{\rm 条指令/秒}}=2000{\rm 秒}$$

计算机 B 花的时间为:

$$\frac{50 \bullet 10^6 {\rm lg} 10^6 {\rm 条指令}}{10^7 {\rm 条指令/秒}} \approx 100 {\rm 秒}$$

计算机 B 由于采用了一个运行时间增长得更为缓慢的算法，尽管它用的是效率较低的编译器，运行速度也比计算机 A 快了 20 倍!当对一千万个数据进行排序时，合并排序的优势就更为明显了；这时，插入排序要花大约 2.3 天的时间，合并排序只需不到 20 分钟的时间。一般来说，随着问题规模的增长，合并排序的相对优势也会愈加明显。

算法和其他技术

上面给出的例子说明了算法就像计算机硬件一样，是一种技术。总体的系统性能不仅依赖于选择快速的硬件，还依赖于选择有效的算法。算法领域的研究和其他计算机技术领域一样，正不断地取得”飞速的进展。

读者可能会想，与其他先进的计算机技术(如以下列出的)相比，算法对于当代的计算机是否真的那么重要?

• 具有高时钟主频、流水线技术、超级标量结构的硬件
• 易于使用的、直观的图形用户界面(GUI)面向对象的系统
• 面向对象的系统
• 局域网和广域网技术

答案是“是的”。尽管对于有些应用来说，在应用这一层面上没有什么特别明显的算法方面的要求(例如，一些简单的 Web 应用就是这样的)，但大多数问题对算法还是有一定程度要求的。例如，假设有一种基于 Web 的服务，它用于确定如何从一个地方旅行至另一个地方。(在写作本书时，已经有了好几种这样的服务了.)其实现将依赖于快速的计算机硬件、图形用户界面、广域网技术，甚至还可能要依赖于面向对象技术。然而，除此之外，它还需要为某些操作设计算法，如寻找路由(很可能采用最短路径算法)、显示地图、插入地址等。

此外，即使是那些在应用层面上对算法性内容没什么要求的应用，其实也是相当依赖于算法的。该应用要依赖于快速的计算机硬件吧?硬件的设计就要用到算法。该应用要用到图形用户界面吧?任何 GUI 的设计也要依赖于算法。该应用要依赖于网络技术吧?网络路由对算法也有着很大的依赖。该应用是采用某种非机器代码的语言编写而成的吧?那么，它就要由编译器、解释器或汇编器来处理，所有这些软件都要大量用到各种算法。算法是当代计算机中用到的大部分技术的核心。

随着计算机性能的不断增长，可以利用计算机来解决比以往更大的问题。从上文有关插入排序与合并排序的比较中可以看出，正是对于更大的问题规模，不同算法在效率方面的差异才会变得特别显著。 是否拥有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。利用当代的计算技术，无需了解很多算法方面的东西，也可以完成-一些任务。但是，有了良好的算法基础和背景的话，可以做的事就要多得多了。

练习

• 1.2-1 给出一个实际应用的例子，它在应用这一层次上要求有算法性的内容。讨论其中所涉及算法的功能。
• 1.2-2 假设我们要 比较在同一台计算机上插入排序和合并排序的实现。对于规模为 n 的输人，插入排序要运行 8n2 步，而合并排序要运行 64nlgn 步。当 n 取怎样的值时，插入排序的性能要优于合并排序?
• 1.2-3 对于一个运行时间为 100n2 的算法，要使其在同一台机器上，比一个运行时间为 2”的算法运行得更快，n 的最小取值是多少?

思考题

• 1-1 算法运行时间的比较

对于下表中的每一个函数 $f(n)$ 和时间 $t$，求出可以在时间 t 内被求解出来的问题的最大规模 $n$。假设解决该问题的算法解决该问题需要 $f(n)$ 微秒。

	1 秒	1 分钟	1 小时	1 天	1 个月	1 年	1 世纪
${\rm lg}n$
$\sqrt{n}$
$n$
$n{\rm lg}n$
$n$
$n^2$
$n^3$
$n!$

本章注记

有许多全面介绍算法这-主题的书都是非常不错的，如 Aho、Hoperoft 和 Ulman[5,6], Baase 和 Van Gelder[26], Brassard 和 Bratley[46, 47]，Goodrich 和 Tamassia[ 128]，Horowitz, Sahni 和 Rajasekaran[ 158]，Kingston [179]，Knuth[182， 183， 185]， Kozen[193]， Manber [210]，Mehlhorn[217, 218, 219], Purdom 和 Brown[ 252]，Reingold, Nievergelt 和 Deo[257], Sedgewick[269], Skiena[280]， 以及 Wil[315]等著作。Bentley[39, 40]和 Gonne[126]对算法 设计中- -些更具体实际的问题进行了讨论。对算法这一领域的综述可以参见《Handbook of Theoretical Computer Science, Volume A)[302]，以及《CRC Handbook on Algorithms and Theory of Computation>[24]. Gusfield[136]. Pevzner[240]、 Setubal 和 Medinas[272]. Waterman[309]等教材则对计算生物学中用到的各种算法做了概述性的介绍。