下载掌阅APP，畅读海量书库
立即打开
如果你是一个计算机专业人士，那么你最好关注计算机算法！不仅仅是因为算法是计算机的核心，而且算法就像计算机的其他技术一样。你可以为了买一个最新、最好的处理器而花大价钱，但是你更需要在其上运行好的算法以使你的钱花得值。
这里有一个例子来说明算法确实是一门技术。在第3章中，我们将会看到几个将 n 个元素按升序排列的算法。其中一些算法的运行时间增长量级是 n 2 ，而另一些算法的运行时间增长量级仅仅为 n lg n 。什么是lg n 呢？它是 n 的以2为底的对数，或记为log 2 n 。计算机科学家如此频繁地使用以2为底的对数，以至于就像数学家和科学家使用缩写ln n 来表示自然对数log e n 一样，计算机科学家也将以2为底的对数表示成缩写形式。因为函数lg n 是指数函数的逆，所以它随着 n 的变化会相当地缓慢增长。如果 n =2 x ，那么 x =lg n 。例如，2 10 =1024，因此lg1024仅仅是10；同样地，2 20 =1048576，因此lg 1048576仅仅等于20；且2 30 =1073741824意味着lg 1073741824仅仅等于30。因此 n lg n 相对于 n 2 ，它是将因子 n 换成了lg n ，这是一种非常方便的表示方式。
让我们将这个例子具体化。假设我们选择在一个较快的计算机（计算机A）上执行一个运行时间为 n 2 的排序算法，而在一个运行速度较慢的计算机上（计算机B）上执行一个运行时间为 n lg n 的排序算法，并让它们均对一个包含着1000万个数字的数组进行排序。（尽管1000万个数看起来很多，如果这些数字是8字节整数，那么输入大约会占用80兆字节，对于一个低廉的笔记本电脑而言，这能够适配主存。）假设计算机A每秒执行100亿条指令（比本书写至此时任何计算机的执行速度更快），而计算机B每秒仅仅能执行1000万条指令，因此计算机A在计算机性能上比计算机B快1000倍。为了使得这个差异更明显，假定世界上具有最精湛技术的程序员为计算机A使用机器语言进行编码，并且结果的代码会需要2 n 2 条指令来实现对 n 个数字的排序，而对计算机B进行编码的仅仅是一个普通程序员，他会使用一个带有低效编译器的高级语言，使得最终编码需要50 n lg n 条指令。为了对1000万个数进行排序，计算机A需要花费的时间为：
这超过了5.5个小时，而计算机B会花费：
该时间不到20分钟。通过使用一个运行时间增长较慢的算法，即使是使用一个较次的编译器，计算机B的运行速度也会比计算机A的运行速度快17倍！当我们对1亿个数字进行排序时，运行时间为 n lg n 的算法的优点会更加显著：运行在计算机A上的时间复杂度为 n 2 的排序算法所花费的时间会超过23天，而运行在计算机B上的时间复杂度为 n lg n 的这个算法所耗费的时间会在4个小时以下。一般而言，当问题规模增加时，时间复杂度为 n lg n 的算法的相对优势也会更加明显。
即使我们看到了计算机硬件方面的不断改进和发展，但是整个系统的性能不仅仅依靠选择运行较快的硬件或者高效的操作系统，选择高效的算法对提升系统的性能也同样重要。就像在其他计算机技术上所做出的重要改进一样，在计算机算法上也在进行着相应的改进。