1.2　作为一种技术的算法

假设计算机是无限快的并且计算机存储器是免费的，你还有什么理由来研究算法吗？即使只是因为你还想证明你的解法会终止并以正确的答案终止，那么回答也是肯定的。

如果计算机无限快，那么用于求解某个问题的任何正确的方法都行。也许你希望你的实现在好的软件工程实践的范围内（例如，你的实现应该具有良好的设计与文档），但是你最常使用的是最容易实现的方法。

当然，计算机也许是快的，但它们不是无限快。存储器也许是廉价的，但不是免费的。所以计算时间是一种有限资源，存储器中的空间也一样。你应该明智地使用这些资源，在时间或空间方面有效的算法将帮助你这样使用资源。
11

效率

为求解相同问题而设计的不同算法在效率方面常常具有显著的差别。这些差别可能比由于硬件和软件造成的差别要重要得多。

作为一个例子，第2章将介绍两个用于排序的算法。第一个称为插入排序，为了排序n个项，该算法所花时间大致等于c1n2，其中c1是一个不依赖于n的常数。也就是说，该算法所花时间大致与n2成正比。第二个称为归并排序，为了排序n个项，该算法所花时间大致等于c2nlgn，其中lgn代表log2n且c2是另一个不依赖于n的常数。与归并排序相比，插入排序通常具有一个较小的常数因子，所以c1

作为一个具体的例子，我们让运行插入排序的一台较快的计算机（计算机A）与运行归并排序的一台较慢的计算机（计算机B）竞争。每台计算机必须排序一个具有1000万个数的数组。（虽然1000万个数似乎很多，但是，如果这些数是8字节的整数，那么输入将占用大致80MB，即使一台便宜的便携式计算机的存储器也能多次装入这么多数。）假设计算机A每秒执行百亿条指令（快于写本书时的任何单台串行计算机），而计算机B每秒仅执行1000万条指令，结果计算机A就纯计算能力来说比计算机B快1000倍。为使差别更具戏剧性，假设世上最巧妙的程序员为计算机A用机器语言编码插入排序，并且为了排序n个数，结果代码需要2n2条指令。进一步假设仅由一位水平一般的程序员使用某种带有一个低效编译器的高级语言来实现归并排序，结果代码需要50nlgn条指令。为了排序1000万个数，计算机A需要
2·(107)2条指令1010条指令/秒=20000秒(多于5.5小时)

而计算机B需要
12
50·107lg107条指令107条指令/秒≈1163秒(少于20分钟)

通过使用一个运行时间增长较慢的算法，即使采用一个较差的编译器，计算机B比计算机A还快17倍！当我们排序1亿个数时，归并排序的优势甚至更明显：这时插入排序需要23天多，而归并排序不超过4小时。一般来说，随着问题规模的增大，归并排序的相对优势也会增大。

算法与其他技术

上面的例子表明我们应该像计算机硬件一样把算法看成是一种技术。整个系统的性能不但依赖于选择快速的硬件而且还依赖于选择有效的算法。正如其他计算机技术正在快速推进一样，算法也在快速发展。

你也许想知道相对其他先进的计算机技术（如以下列出的），算法对于当代计算机是否真的那么重要：

先进的计算机体系结构与制造技术

易于使用、直观的图形用户界面（GUI）

面向对象的系统

集成的万维网技术

有线与无线网络的快速组网

回答是肯定的。虽然某些应用在应用层不明确需要算法内容（如某些简单的基于万维网的应用），但是许多应用确实需要算法内容。例如，考虑一种基于万维网的服务，它确定如何从一个位置旅行到另一个位置。其实现依赖于快速的硬件、一个图形用户界面、广域网，还可能依赖于面向对象技术。然而，对某些操作，如寻找路线（可能使用最短路径算法）、描绘地图、插入地址，它还是需要算法。

而且，即使是那些在应用层不需要算法内容的应用也高度依赖于算法。该应用依赖于快速的硬件吗？硬件设计用到算法。该应用依赖于图形用户界面吗？任何图形用户界面的设计都依赖于算法。该应用依赖于网络吗？网络中的路由高度依赖于算法。该应用采用一种不同于机器代码的语言来书写吗？那么它被某个编译器、解释器或汇编器处理过，
13所有这些都广泛地使用算法。算法是当代计算机中使用的大多数技术的核心。

进一步，随着计算机能力的不断增强，我们使用计算机来求解比以前更大的问题。正如我们在上面对插入排序与归并排序的比较中所看到的，正是在较大问题规模时，算法之间效率的差别才变得特别显著。

是否具有算法知识与技术的坚实基础是区分真正熟练的程序员与初学者的一个特征。使用现代计算技术，如果你对算法懂得不多，你也可以完成一些任务，但是，如果有一个好的算法背景，那么你可以做的事情就多得多。

练习

1.2-1　给出在应用层需要算法内容的应用的一个例子，并讨论涉及的算法的功能。

1.2-2　假设我们正比较插入排序与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行8n2步，而归并排序运行64nlgn步。问对哪些n值，插入排序优于归并排序？

1.2-3　n的最小值为何值时，运行时间为100n2的一个算法在相同机器上快于运行时间为2n的另一个算法？