9.1. 分析问题¶

你最常用"算法"分析的技术来分析一个 算法 ， 或算法作为 程序 的实例化。 你也可以用同样的技术来分析一个 问题 的代价。 我们要问的关键问题是：一个问题有多难？ 当然，我们应当预期，在某种意义上， 对一组记录进行排序的问题比在一组记录中查找给定键值的问题更难。 当然，我们所知道的用于对某些记录排序的算法， 似乎比我们所知道的用于查找这些相同记录的算法代价更高。

我们需要的是关于问题 上界 和 下界 的实用定义。

有人一开始可能会认为，问题的上界是求解该问题的任何算法 所能达到的难度的上限。 但我们可以把算法写得多糟就多糟，所以这种说法没有用。 相反，有用的说法是：一个问题的难度只取决于我们能做到什么。 换句话说，我们应当把问题的上界定义为我们所知道的求解该问题的 最好 算法。 当然，每当谈论界时，都必须说明它适用于何时。 我们其实应当说：我们所知道的最坏情况下的最好算法， 或我们所知道的平均情况下的最好算法。

但给出问题的下界意味着什么？ 下界指的是任何算法都必须付出的最小代价。 例如，在未排序的线性表中查找时，我们必须查看每一条记录。 对线性表排序时，我们必须查看每一条记录（甚至只是为了知道它是否已排序）。

证明一个算法（或程序）属于 \(\Omega(f(n))\) ， 比证明一个问题属于 \(\Omega(f(n))\) 要容易得多。 一个问题属于 \(\Omega(f(n))\) 意味着 每一个 求解该问题的算法都属于 \(\Omega(f(n))\) ， 甚至包括我们尚未想到的算法！ 换句话说，每一个算法都必须至少付出这样的代价。 因此，要证明下界，我们需要一个即使对我们不知道的算法也成立的论证。

到目前为止，我们所有的算法分析例子给出的都是"显然"的结果， 大 O 总是与 \(\Omega\) 吻合。 要理解大 O、 \(\Omega\) 和 \(\Theta\) 记法如何被恰当地用来 描述我们对一个问题或算法的认识， 最好考虑一个你原本了解不多的例子。

让我们先来看分析排序问题的过程，了解它是如何进行的。 在最坏情况下，任何排序算法可能付出的最小代价是多少？ 算法至少必须查看输入中的每一个元素， 仅仅是为了确定输入确实已排好序。 因此，任何排序算法都必须至少花费 \(cn\) 的时间。 对许多问题而言，只要观察到 \(n\) 个输入中的每一个都必须被查看， 就能轻松得出 \(\Omega(n)\) 的下界。

在你以前学习计算机科学时， 可能见过一个在最坏情况下运行时间属于 \(O(n^2)\) 的排序算法例子。 在一年级程序设计课程中通常作为例子给出的 简单冒泡排序和插入排序算法， 最坏情况下的运行时间属于 \(O(n^2)\) 。 因此，可以说排序问题的上界是 \(O(n^2)\) 。 我们如何缩小 \(\Omega(n)\) 与 \(O(n^2)\) 之间的差距？ 可能存在更好的排序算法吗？ 如果你想不到任何最坏情况增长率优于 \(O(n^2)\) 的算法， 也没有发现任何分析技术能证明 最坏情况下排序问题的最小代价大于 \(\Omega(n)\) ， 那么你就无法确定是否存在更好的算法。

许多好的排序算法在最坏情况下的运行时间属于 \(O(n \log n)\) 。 这大大缩小了差距。 有了这个新认识，我们现在得到 \(\Omega(n)\) 的下界 和 \(O(n \log n)\) 的上界。 我们是否应当寻找更快的算法？ 许多人尝试过，都没有成功。 幸运的是（或许是不幸？）， 排序下界 证明了一个事实：任何排序算法在最坏情况下的运行时间 都必须属于 \(\Omega(n \log n)\) 。 [1] 这个证明是算法分析领域最重要的结果之一， 它意味着对规模为 \(n\) 的最坏情况输入， 任何排序算法都不可能比 \(c n \log n\) 运行得更快。 因此，我们可以断定，最坏情况下排序问题是 \(\Theta(n \log n)\) ， 因为上界和下界已经吻合。

知道一个问题的下界并不会给你一个优秀的算法。 但它确实有助于你知道何时停止寻找。 如果问题的下界与算法的上界吻合（在常数因子范围内）， 那么我们就知道，能找到的更好算法也只能好一个常数因子。

总之：问题的上界是你能做到的最好结果， 而问题的下界是你必须付出的最少工作量。 如果两者相同，我们就说我们真正理解了这个问题。