假设计算机无限快,并且计算机存储器是免费的,那么你还有任何理由来研究算法吗?如果你没有别的理由,就是仍然希望证明你的解决方案能够终止并给出正确的结果的话,那么答案就是“是的”。
如果计算机无限快,那么对于某一个问题来说,任何一个可以解决它的正确方法都是可以的。你很可能希望自己的实现能够符合良好的软件工程实践要求(亦即,具有良好的设计和文档说明),但往往会采用最容易实现的方法。
当然,计算机可以做得很快,但还不能是无限快。存储器可以做到很便宜,但不会是免费的。因此,计算时间是一种有限的资源,存储空间也是一种有限的资源。这些有限的资源必须被有效地使用,那些时间和空间上有效的算法就有助于做到这一点。
效率
解决同一问题的各种不同算法的效率常常相差很大。这种效率上差距的影响往往比硬件和软件方面的差距还要来得大。
例如,在第 2 章中,我们将介绍两个排序算法。第一个称为插入排序算法,对 个数据项进行排序的时间大约等于 ?,其中 是一个不依赖于 n 的常量。亦即,该算法所需的时间大致正比于 n2。第二个是合并排序算法,它排序 n 个数据项所需的时间大约是 ,其中 表示 log2n, C2 是另一个同样也不依赖于 n 的常量。插入排序算法与合并排序算法相比,通常有着更小的常量因子,即 。后面我们还将看到,与对输入规模 n 的依赖相比,常量因子对运行时间的影响要小得多。合并排序算法的运行时间中有个因子 lgn,而插入排序算法的运行时间中有