谈谈基于比较的排序算法的复杂度下界

基于比较的排序算法的复杂度下界是 $Ω (n \log n)$ ，对于学过算法的人来说，这是一个基本常识。但它是怎么来的呢？

让未知世界无机可乘

在讨论排序之前，这里引入一个小游戏，为后续分析做一些准备。

这个游戏很简单。具体来说，我从整数范围 $[a, b)$ 当中（其中 $b > a$ ）选择一个数字，由你来猜。你可以通过提问的方式，缩小答案范围。但这些问题的答案只能是「是」或者「否」，并且我保证会如实作答。现在的问题是，何种策略能够在所有情况下，尽可能快地猜到正确答案？

这个问题对稍有 CS 基础的读者来说应该是仅凭直感就能回答的：二分搜索呗。具体来说，先提问目标数字是不是位于 $[a, ⌈ \frac{a + b}{2} ⌉)$ 之间，然后根据答案继续提问下去，直到得到正确答案。显然，它的时间复杂度是 $Θ (\log_{2} (b - a))$ 。

那么问题来了。为什么这样的策略在平均情况下是最优的？换句话说，它为什么这样快呢？

为了说明这个问题，我们需要换一个角度去思考这个游戏。考虑到区间 $[a, b)$ 当中一共有 $b - a$ 个整数。因此，「确定随机选择的数字为 $c$ 」这个命题所携带的信息量应当是 $- \log_{2} \frac{1}{b - a}$ 。在游戏中，每次猜测 + 回答，事实上构成了一个命题。若根据这一系列的命题能够确定随机选择的数字，则这一系列命题所携带的信息量之和应该超过 $- \log_{2} \frac{1}{b - a}$ 。那么，要尽可能快地找到这个数字，本质上就是要系列命题中的每一个都尽可能携带多的信息量，并且相互不重叠。

顺着这个思路往下想。由于游戏中规定了猜测的答案只能是「是」或「否」。我们定义答案为「是」的概率为 $p$ ，相应答案为「否」的概率为 $1 - p$ 。那么这个猜测 + 答案形成的命题所携带的信息量为 $- p \log_{2} p - (1 - p) \log_{2} (1 - p)$ 。显然，要使得该命题所携带的信息量最大，就要让 $p = \frac{1}{2}$ 。这就是为什么二分搜索快的原因了。

这里从信息论的角度，用了一些公式去阐述问题。换成通俗的语言来描述，就是用二分搜索的策略，能够让每一次猜测都排除一半的可能性，并且无论如何都能排除一半的可能性。换而言之，二分搜索的策略，让未知世界无机可乘。

排序问题的重述

首先这里需要重新表述一下排序问题。

排序问题的本质可以理解为在 $n$ 个（不同）数的 $n!$ 种全排列中，选出一种，使其满足某种偏序关系（一般是小于或大于）。

现在我们考虑，基于元素比较的排序方法，每一次判定 $a < b$ ，都相当于回答了一次「是否问题」。按照已有的知识，若要尽可能快地完成排序，就要让每一次大小判断的结果落在两种答案之一的概率接近；若不然，则这次比较带来的信息量较小，也就需要更多次的比较来完成排序。那么，基于比较的方法，至少需要多少次比较才能完成排序呢？换而言之，基于比较的排序算法，其复杂度下界是什么呢？

基于比较的排序算法的复杂度下界

现在我们已知，有 $n!$ 种可能的不同排列方式。假设我们有一个完美的算法，能够每次去除剩余可能性中的一半，则我们需要 $\log_{2} n!$ 次比较。这就是基于比较的排序算法的复杂度下界： $Ω (\log n!)$ 。

现在我们把它变换成比较好看的形式。考虑斯特灵级数

$n! = \sqrt{2 π n} (\frac{n}{e})^{n} (1 + \frac{1}{12 n} + \frac{1}{288 n^{2}} + \dots),$

这也就是说

$\ln n! = n \ln n - n + \frac{1}{2} \ln (2 π n) + \frac{1}{12 n} - \frac{1}{360 n^{3}} + \dots .$

因此，在渐进的意义下， $\log n! = Θ (n \log n)$ 。这说明，基于比较的排序算法的复杂度下界是 $Ω (n \log n)$ 。