4.2. 排序的下界¶
4.2.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)\) 时间排序算法改进超过一个常数因子。
下面是一些复习题，用来检验你是否理解了这一证明。
