16. 排序的下界¶
16.1. 排序的下界¶
到目前为止，你已经见过许多算法分析。 这些分析通常定义算法在最坏情况和平均情况下的上界与下界。 对你所知道的大多数算法而言，分析一直很容易。 本模块考虑一项更困难的任务：分析一个 问题 的代价，而不是一个 算法 的代价。 一个问题的上界可以定义为已知最快算法的渐近代价。 下界则定义求解该问题的 任意 算法所能达到的最好代价，包括尚未 发明的算法。 一旦问题的上界与下界相遇，我们就知道未来不可能有（在渐近意义下） 更高效的算法。
对问题下界的一个简单估计，可以通过衡量必须读取的输入规模和必须 写出的输出规模来得到。 当然，任何算法的效率都不可能超过问题的 I/O 时间。 由此我们看到，排序问题无法被 任意 算法在少于 \(\Omega(n)\) 的 时间内解决，因为读取和写出待排序的 \(n\) 个值至少需要 \(n\) 步。 换个角度说，任何排序算法都至少要查看每一个输入值，才能识别输入值 是否已按序排列。 因此，根据我们目前对排序算法和输入规模的了解，我们知道排序 问题 被界定在 \(\Omega(n)\) 与 \(O(n \log n)\) 之间。
计算机科学家花了大量时间设计高效通用的排序算法，但从未有人找到在 最坏情况或平均情况下快于 \(O(n \log n)\) 的算法。 我们是否应该继续寻找更快的排序算法？ 还是说，我们能通过找到一个更紧的下界来证明不存在更快的排序算法？
本节介绍计算机科学中最重要、最有用的证明之一：在最坏情况下，任何 基于键比较的排序算法都不可能快于 \(\Omega(n \log n)\) 。 这个证明之所以重要，有三个原因。 第一，知道广泛使用的排序算法在渐近意义下是最优的，令人安心。 特别是，它意味着你无需为了寻找一个 \(O(n)\) 排序算法而撞墙。 （或者至少不是任何以键比较为基础的算法。 但很难想象完全不进行比较该怎么排序。 就连基数排序也要做比较，只是方式相当不同。） 第二，这个证明是我们对任何问题所拥有的少数非平凡下界证明之一； 也就是说，它提供了相对少见的实例之一，其中我们的下界比单纯衡量 输入和输出的规模更紧。 因此，它为证明其他问题的下界提供了一个有用的范例。 最后，知道排序的下界，又反过来为那些其解可作为排序算法基础的其他 问题给出了下界。 从一个问题的渐近界推导出另一个问题的渐近界，这一过程称为 归约 。
除了基数排序和箱排序之外，我们研究过的所有排序算法都基于两个 键值的直接比较来做决定。 例如，插入排序会依次比较待插入到已排序线性表中的值，直到与线性表 中下一个值的比较失败为止。 相比之下，基数排序不直接比较键值。 所有决定都基于键值中特定位的数值，因此可以采用不涉及直接 键比较的排序方法。 当然，基数排序最终并没有提供比基于比较的排序更高效的排序算法。 因此，实验经验表明基于比较的排序是一种好方法。
（实际上，事实比这句话所暗示的更强。 现实中，基数排序同样依赖比较，因此可以用本节所用的技术来建模。 结果是，即便对于看起来像基数排序的算法，在一般情况下也有 \(\Omega(n \log n)\) 的下界。）
任何比较排序在最坏情况下都需要 \(\Omega(n \log n)\) 次比较， 这一证明的结构如下。 首先，基于比较的决定可以建模为树中的分支。 这意味着任何基于记录之间比较的排序算法都可以看作一棵二叉树，其 结点对应比较，其分支对应可能的结果。 接着，证明所得树中最少叶结点数是 \(n\) 的阶乘。 最后，证明具有 \(n!\) 个叶结点的树的最小深度属于 \(\Omega(n \log n)\) 。
排序具有 \(\Omega(n \log n)\) 下界这一证明，依赖于 判定树 的概念。 判定树是一棵二叉树，可以建模任何做二值决定的算法的处理过程。 每个（二值）决定都用树中的一个分支表示。 为建模排序算法，我们把所有键值的比较都计为决定。 如果比较两个键，且第一个小于第二个，就把它建模为判定树中的 左分支。 在第一个值大于第二个值的情况下，算法走右分支。
下面这个可视化演示了判定树以及排序下界的证明。
任何在最坏情况下需要 \(\Omega(n \log n)\) 次比较的排序算法， 在最坏情况下都需要 \(\Omega(n \log n)\) 的运行时间。 因为任何排序算法都需要 \(\Omega(n \log n)\) 的运行时间， 所以排序问题也需要 \(\Omega(n \log n)\) 的时间。 我们已经知道有运行时间为 \(O(n \log n)\) 的排序算法，因此可以 得出结论：排序问题需要 \(\Theta(n \log n)\) 的时间。 作为推论，我们知道任何基于比较的排序算法都不可能把现有的 \(\Theta(n \log n)\) 时间排序算法改进超过一个常数因子。
下面是一些复习题，用来检验你是否理解了这一证明。
