1.1. 计算极限¶

截至目前，你已经学习了许多可以用于各种各样问题的数据结构，以及大量高效算法的例子。 一般来说，我们的查找算法力求在最坏情况下用 \(O(\log n)\) 时间找到一条记录， 排序算法则力求达到 \(O(n \log n)\)。 你可能已经遇到过一些渐近复杂度更高的算法。 无论是 Floyd 全对最短路径算法 还是标准矩阵乘法，其运行时间都为 \(\Theta(n^3)\) （不过对两者而言，由于都作用于 \(n \times n\) 矩阵，被处理的数据量为 \(\Theta(n^2)\)）。

我们之所以能高效地解决许多问题，是因为我们有（并且选择使用）高效的算法。 对于任何你知道 某种 算法的问题，总是有可能写出一个低效的算法来"解决"该问题。 例如，考虑一种排序算法，它逐一测试输入的所有排列，直到找到能给出有序列表的正确排列。 该算法的运行时间会高得不可接受，因为它与排列的数目成正比（对 \(n\) 个输入来说排列数为 \(n!\)）。 在求解 最小代价生成树问题 时，如果我们要测试每一种可能的边子集以确定哪一个能形成最短的最小生成树，那么对于具有 \(|{\rm E}|\) 条边的图，工作量将与 \(2^{|{\rm E}|}\) 成正比。 幸运的是，对这两个问题我们都有更巧妙的算法，可以在（相对）较短的时间内找到答案，而无需显式测试每一个可能的解。

遗憾的是，有许多计算问题，即使最佳可能的算法也需要很长的运行时间。 一个简单的例子是 汉诺塔问题， 它需要 \(2^n\) 次移动才能"解决"具有 \(n\) 个圆盘的塔。 任何解决汉诺塔问题的计算机程序都不可能以低于 \(\Omega(2^n)\) 的时间运行，因为必须输出那么多次移动。

除了那些解 必然 需要很长时间才能运行的问题（或许因为解本身就非常大）之外， 还有许多问题我们根本不知道是否存在高效的算法。 对于这类问题，我们所知的最佳算法都非常慢，但也许还有更好的算法等待被发现。

虽然运行时间很高的问题很糟糕，但根本无法解决的问题更加糟糕！ 这样的问题（被称为 不可解问题） 确实存在。 这类问题的经典例子是判定任意计算机程序在处理指定输入时是否会陷入无限循环。 这就是著名的 停机问题。