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

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

让未知世界无机可乘

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

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

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

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

为了说明这个问题,我们需要换一个角度去思考这个游戏。考虑到区间 $[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!$ 次比较。这就是基于比较的排序算法的复杂度下界:$\Omega (\log n!)$。

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

$$ n! = \sqrt{2\pi n}\Bigl(\frac{n}{\mathrm{e}}\Bigr)^{n}\Bigl(1 + \frac{1}{12n} + \frac{1}{288n^2} + \cdots\Bigr), $$

这也就是说

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

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


您的鼓励是我写作最大的动力

俗话说,投资效率是最好的投资。 如果您感觉我的文章质量不错,读后收获很大,预计能为您提高 10% 的工作效率,不妨小额捐助我一下,让我有动力继续写出更多好文章。


撰写评论

写了这么多年博客,收到的优秀评论少之又少。在这个属于 SNS 的时代也并不缺少向作者反馈的渠道。因此,如果你希望撰写评论,请发邮件至我的邮箱并注明文章标题,我会挑选对读者有价值的评论附加到文章末尾。