7.4　下界：为什么比较排序绕不开 $n \log n$

学习目标：学完本节，你能

用决策树模型推导出比较排序的下界 $\Omega(n \log n)$；
说清 $O(n \log n)$ 为什么不是一个"还不错的成绩"，而是理论最优；
说出这条下界的适用边界 —— 以及谁能突破它。

先修：7.3（比较模型）、1.2（对数）。 固定术语：决策树、下界、比较排序、非比较排序。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、决策树：排序就是"问问题"

把排序算法想象成一个"猜谜游戏"：

你面对一个乱序的数组，但不知道它的具体内容（只知道有 $n$ 个元素）
你唯一能做的动作是问一个"是/否"的问题 —— 也就是比较两个元素的大小
你的目标是确定这个数组的正确排序结果

每一次比较，就是一次"是/否"提问。整个比较过程构成一棵决策树。

以 $n = 3$ 为例（数组 [a, b, c]，有 $3! = 6$ 种可能的排列）：

                    比较 a 和 b
                   /            \
              a < b              a > b
             /      \           /      \
       比较 b,c   比较 a,c   比较 b,c   比较 a,c
        /   \      /   \      /   \      /   \
     abc   acb   ...  ...   ...  ...   ...  ...

每个叶子节点对应一种可能的排列结果。 算法必须能在比较若干次之后，唯一确定当前是哪种排列。

关键观察：

$n$ 个元素一共有 $n!$ 种不同的排列，所以决策树至少要有 $n!$ 个叶子。

二、推导下界

现在做一个简单的计数论证。

设算法最多需要 $k$ 次比较。

一棵深度为 $k$ 的二叉树，最多有多少个叶子？

深度 0：1 个叶子
深度 1：最多 2 个叶子
深度 2：最多 4 个叶子
深度 $k$：最多 $2^k$ 个叶子

而我们需要至少 $n!$ 个叶子（要能区分 $n!$ 种排列）。所以：

$$2^k \ge n!$$

两边取以 2 为底的对数：

$$\boxed{k \ge \log_2(n!)}$$

这就是比较排序的下界。

用大白话说：

每次比较最多把可能性分成两半。要从 $n!$ 种可能性中确定唯一的一种，至少需要 $\log_2(n!)$ 次比较。

三、实测：$n!$ 有多大，$\log_2(n!)$ 有多小

先感受一下 $n!$ 的增长：

           n |                        n! |     log2(n!)
------------------------------------------------------------------
           3 |                         6 |          2.6
           5 |                       120 |          6.9
          10 |                 3,628,800 |         21.8
          20 | 2,432,902,008,176,640,000 |         61.1
          50 |                   3×10^64 |        214.2

$n = 50$ 时，排列数达到 $3 \times 10^{64}$ —— 但 $\log_2$ 之后只有 214。

再看下界和 $n \log_2 n$ 的关系：

             n |     下界 log2(n!) |        n*log2(n) |          差距 |    差距/n
------------------------------------------------------------------------------------
            10 |             21.8 |            33.2 |          11.4 |    1.1405
           100 |            524.8 |           664.4 |         139.6 |    1.3961
         1,000 |          8,530.9 |         9,965.8 |       1,434.9 |    1.4349
        10,000 |        118,458.5 |       132,877.1 |      14,418.6 |    1.4419
       100,000 |      1,516,701.5 |     1,660,964.0 |     144,262.5 |    1.4426
     1,000,000 |     18,488,885.6 |    19,931,568.9 |   1,442,683.3 |    1.4427

最后一列稳定在 1.4427 附近 —— 这正是 $\log_2 e$ 的值。

所以有一个精确的近似公式：

$$\log_2(n!) \approx n \log_2 n - 1.4427 n + O(\log n)$$

换句话说：下界和 $n \log_2 n$ 只差一个线性项 $1.44n$。

对于大的 $n$，$1.44n$ 相对于 $n \log n$ 可以忽略（$n = 10^6$ 时，139 万的差距 vs 1993 万的总量）。

所以工程上我们说："比较排序的下界是 $\Omega(n \log n)$"。

四、这意味着什么

这条下界推翻了一个很常见的想法：

~~"冒泡排序太慢了，我设计一个更聪明的算法，应该能到 $O(n)$ 吧？"~~

做不到。 只要你的算法是：

只通过比较元素大小来获取信息（符合比较模型）
对任意输入都要给出正确答案（最坏情况分析）

那么无论你怎么设计，最坏情况下至少要比较 $\log_2(n!)$ 次 —— 也就是 $\Omega(n \log n)$。

看几个具体的数字感受一下：

           n |                需要区分的情况数 n! |         至少几次比较
--------------------------------------------------------
        10 |                  3,628,800 |             22
        20 |  2,432,902,008,176,640,000 |             62
        30 | 265,252,859,812,191,058,636,308,480,000,000 |            108

$n = 30$ 时，$30!$ 是一个 33 位数 —— 但只需要 108 次比较就能区分它们。

这条下界最重要的推论是：

$O(n \log n)$ 不是"还不错的成绩"，而是"理论最优"。

快速排序、归并排序、堆排序都达到了这个量级 —— 它们在这条赛道上已经到顶了，不可能再快。

所以第 8 章要比较的不是"谁能突破 $n \log n$"，而是"在都是 $n \log n$ 的前提下，谁的常数更小、谁的性质更好"。

关于"下界"的一个常见误解：

下界说的是"不可能少于这么多"，不代表"一定能做到这么多"。

看小规模的实际最优比较次数：

      n |     log2(n!) |       向上取整 |         实际最优 | 说明
--------------------------------------------------------------------------
      2 |        1.000 |          1 |            1 | 比较 1 次就够了
      3 |        2.585 |          3 |            3 | 需要 3 次（下界 2.58 不够）
      4 |        4.585 |          5 |            5 | 需要 5 次（下界 4.58 不够）
      5 |        6.907 |          7 |            7 | 需要 7 次

$n = 3$ 时下界是 2.58，向上取整是 3 —— 实际确实能做到 3 次。 $n = 4$ 时下界是 4.58，向上取整是 5 —— 实际确实能做到 5 次。

但 $n$ 再大一些，"能达到下界"的算法就越来越难写，而且常数极大。

工程上不追求"达到理论下界"，而是追求"达到 $n \log n$ 这个量级，同时常数尽量小"。

这就是为什么快速排序（平均常数小、原地排序）比归并排序（要额外空间）更常用 —— 虽然它们的量级完全相同。

五、那还能更快吗？

能 —— 但必须跳出比较模型。

这条下界的前提是"只能通过比较获取信息"。 如果你直接利用元素的值本身，下界就不适用了。

举个例子：排 100 万个 0 到 100 之间的整数。

比较排序：至少 $\log_2(10^6!) \approx 1.85 \times 10^7$ 次比较
但如果你知道取值范围只有 0~100：直接数一下每个数出现几次，然后按顺序输出就行 —— $O(n)$ 就够了

这就是计数排序（Counting Sort）的思路。

不去比较元素之间的大小，而是直接统计「每个值出现了几次」，
然后按值的顺序依次输出。

这类算法称为非比较排序，8.4 节会详细讲：

算法	复杂度	前提条件
计数排序	$O(n + k)$（$k$ 是取值范围）	值域有限且不大
基数排序	$O(d \cdot n)$（$d$ 是位数）	能按位拆分

代价是它们对数据有额外要求，通用性不如比较排序 —— 这就是"用适用性换速度"。

但记住这个结论：

"突破 $n \log n$"不是靠更聪明的比较，而是靠"不比较"。

很多人在优化排序时，第一反应是"我要写一个更快的比较排序" —— 方向就错了。正确的问法是："我能利用数据的什么额外信息？"

六、练习

练习 7.4.1（计算）用 $\log_2(n!) \approx n \log_2 n - 1.4427 n$ 估算： (a) $n = 8$ 时的下界 (b) $n = 1000$ 时的下界 (c) 如果一次比较需要 1 纳秒，$n = 10^6$ 时下界对应多少秒？

练习 7.4.2（决策树）画出 $n = 3$ 时排序 [a, b, c] 的决策树。 (a) 树有多少个叶子？ (b) 树的最小深度是多少？ (c) 最坏情况下需要几次比较？

练习 7.4.3（判断）判断对错并说明理由： (a) 因为下界是 $\Omega(n \log n)$，所以冒泡排序和归并排序在最坏情况下一样快。 (b) 存在一个比较排序算法，平均复杂度是 $O(n)$。 (c) 计数排序能排任意整数数组，所以它比快速排序更好。

练习 7.4.4（工程判断）一个系统要排序 1000 万个用户 ID（都是 0 到 999,999,999 之间的整数）。 (a) 用比较排序，下界是多少次比较？ (b) 用计数排序可行吗？为什么？ (c) 你会选择什么方案？

练习 7.4.5（挑战·证明）请证明：任何比较排序算法，在最坏情况下至少需要 $\lceil \log_2(n!) \rceil$ 次比较。 要求写清每一步的依据，特别是"为什么决策树的叶子数至少是 $n!$"。

七、练习答案

7.4.1

(a) $n = 8$：

$$\log_2(8!) \approx 8 \log_2 8 - 1.4427 \times 8 = 8 \times 3 - 11.54 = 24 - 11.54 = 12.46$$

精确值：$\log_2(40320) \approx 15.30$

近似公式在这里误差较大（因为 $n$ 太小，$O(\log n)$ 那一项还不能忽略）。

这提醒我们：近似公式只在大 $n$ 时好用。 小 $n$ 要用精确值。

(b) $n = 1000$：

$$\log_2(1000!) \approx 1000 \times 9.966 - 1.4427 \times 1000 = 9966 - 1443 = 8523$$

实测表里的精确值是 8,530.9 —— 误差 0.1%，已经非常准了。

(c) $n = 10^6$：

$$\log_2(10^6!) \approx 1.85 \times 10^7 \text{ 次比较}$$

$1.85 \times 10^7$ 纳秒 = 0.0185 秒 ≈ 18.5 毫秒。

注意这个数字：100 万个元素，比较排序的理论下界只要 18.5 毫秒（假设每次比较 1 纳秒）。

实际实现要慢得多（因为还有内存访问、元素移动、缓存未命中等开销），通常在几百毫秒到几秒。

这说明：理论下界和实际耗时之间有巨大的差距 —— "达到 $n \log n$ 量级"只是第一步，常数优化同样重要。

7.4.2

(a) 叶子数 = $3! = 6$ 个。

每个叶子对应一种可能的排列：abc, acb, bac, bca, cab, cba。

(b) 深度至少是 $\lceil \log_2 6 \rceil = 3$。

因为深度为 2 的二叉树最多 $2^2 = 4$ 个叶子，装不下 6 种排列。

(c) 最坏情况下需要 3 次比较。

具体的比较策略：

第 1 次：比较 a 和 b
  假设 a < b

第 2 次：比较 b 和 c
  情况 A：b < c  -> 已知 a < b < c，答案是 abc（2 次搞定）
  情况 B：b > c  -> 已知 a < b 且 c < b，但 a 和 c 的关系未知
                    第 3 次：比较 a 和 c
                      a < c -> acb
                      a > c -> cab

另一支（第 1 次得到 a > b）是对称的。

所以最坏情况下确实只需要 3 次 —— 达到了下界 ✓

有意思的是：这个策略在最好的情况下只要 2 次（当 a < b < c 时）。但最坏情况是 3 次，这才是下界关心的情况。

7.4.3

(a) 错，混淆了"下界"和"实际复杂度"。
- 下界 $\Omega(n \log n)$ 说的是"任何比较排序都不可能比这更快"。
- 冒泡排序是 $O(n^2)$ —— 它远没有达到下界。
- 归并排序是 $O(n \log n)$ —— 它达到了下界。
  
  下界是"及格线"，不是"所有人都在及格线上"。 冒泡排序离及格线还差得远。
(b) 错。 平均情况同样受下界约束。

论证：平均比较次数 ≥ 最坏情况下的下界 / 某种因子。更严格地说，如果平均只要 $c \cdot n$ 次比较，那么决策树的平均深度是 $O(n)$，而树的叶子数 $n!$ 要求树的平均深度至少是 $\Omega(\log(n!)) = \Omega(n \log n)$。

直觉：如果存在一个平均 $O(n)$ 的比较排序，那它必须"大多数情况下很快" —— 但这意味着决策树大部分叶子都很浅，而浅叶子装不下那么多排列（深度 $k$ 的叶子最多覆盖 $2^k$ 种输入）。
(c) 错，而且错得离谱。

计数排序的前提是"值域有限且不大"。它需要开一个大小为 $k$（取值范围）的计数数组。

如果值是 int 范围内的任意整数（$k = 2^{32} \approx 43$ 亿），那计数数组就要 43 亿个元素 —— 内存直接爆掉。

所以计数排序的复杂度 $O(n + k)$ 里，$k$ 不能太大。 只有 $k = O(n)$ 时它才真正比比较排序快。

这是一个典型的"理论复杂度漂亮、实际用不了"的例子。

7.4.4

(a) 下界：

$$\log_2(10^7!) \approx 10^7 \times \log_2(10^7) - 1.4427 \times 10^7$$

$$= 10^7 \times 23.25 - 1.44 \times 10^7$$

$$\approx 2.18 \times 10^8 \text{ 次比较}$$

约 2.18 亿次比较。

(b) 不可行。

用户 ID 的范围是 0 到 999,999,999 —— 计数数组需要 10 亿个元素。

即使每个计数器只占 4 字节，也要 4 GB 内存，而实际只有 1000 万个 ID（利用率 1%）。

这就是"值域太大"的典型情况。

(c) 推荐方案：

方案 1：基数排序（推荐）

把 10 位数字按位拆开，每一位做一次计数排序。每一位的"计数数组"只需要 10 个元素（数字 0~9）。

$$O(d \cdot n) = 10 \times 10^7 = 10^8 \text{ 次操作}$$

比比较排序的 2.18 亿次快一倍多，而且内存只有 $O(n)$。

方案 2：如果 ID 分布在一个较窄的区间

比如实际 ID 都落在 0 到 5000 万之间 —— 那计数数组只需要 5000 万个元素（200 MB），可能可以接受。

方案 3：直接用比较排序

如果数据没有特别的分布特征，用 Array.Sort（内省排序）就够了 —— 现代实现高度优化，实际性能往往比你自己写的非比较排序还好。

工程判断的核心：

不要一看到"下界是 $n \log n$"就急着去用非比较排序。

先问三个问题：

值域有多大？ 太大就不能用计数排序。

能按位拆分吗？ 能就用基数排序。

现成的比较排序够快吗？ 如果 $n$ 只有几万，用哪个都差不多，别过度设计。

7.4.5

证明：任何比较排序算法在最坏情况下至少需要 $\lceil \log_2(n!) \rceil$ 次比较。

第一步：建立决策树模型。

把算法的运行过程表示成一棵二叉树：

每个内部节点代表一次比较（比如"比较 $a_i$ 和 $a_j$"），有两条出边（"$\le$" 和 "$>$"）
每个叶子节点代表算法终止，输出一个排序结果
从根到叶的路径长度 = 这次运行做了多少次比较

第二步：证明叶子数至少是 $n!$。

关键论证：算法必须对每一种可能的输入都输出正确的结果。

对于 $n$ 个元素，一共有 $n!$ 种不同的排列（假设元素两两不同）
如果两种不同的输入排列走到了同一个叶子，那么算法对它们输出了同一个结果
但这两个排列的正确排序结果不同（至少有一个元素的正确位置不同）
所以算法至少对其中一个输出了错误答案 —— 矛盾

因此，不同的输入排列必须走到不同的叶子。叶子数 $\ge n!$。 ∎（第一步）

第三步：由叶子数推出深度下界。

设树的高度（根到叶的最大路径长度）为 $h$。

深度为 $h$ 的二叉树，最多有 $2^h$ 个叶子（证明：用归纳法。深度 0 有 1 个叶子 $= 2^0$；每往下加一层，每个叶子最多分裂成 2 个，所以第 $k$ 层最多 $2^k$ 个。）

由第二步，叶子数 $\ge n!$，所以：

$$2^h \ge n!$$

第四步：取对数。

因为 $2^x$ 是单调递增的，两边取 $\log_2$：

$$h \ge \log_2(n!)$$

又因为 $h$ 必须是整数：

$$h \ge \lceil \log_2(n!) \rceil$$

第五步：得出结论。

树的高度 $h$ 就是最坏情况下的比较次数（最深的叶子对应最多比较次数的那次运行）。

所以：

$$\text{最坏情况比较次数} \ge \lceil \log_2(n!) \rceil$$

证毕。 ∎

这个证明的漂亮之处在于：它完全不关心算法具体怎么实现。

不管你是冒泡、插入、快排还是某个还没被发明出来的算法 —— 只要你符合比较模型，这个论证就成立。

这就是"下界"的力量：它约束的是一整类算法，而不是某一个。

顺带一提：这个证明也解释了为什么"判断两个元素是否相等"这个操作不能减少下界 —— 因为决策树每个节点只有两条边（"是"和"否"）。如果一次比较能有三种结果（小于、等于、大于），那每个节点有三条边，树能装下更多叶子……但你仍然需要先做一次比较才能得到这个三选一的结果，所以每个"信息位"的成本没变。

（严格来说，三路比较的决策树是三叉树，深度下界变成 $\log_3(n!)$ —— 但每次比较仍然只算"一次操作"。而 $\log_3$ 和 $\log_2$ 只差一个常数因子，所以量级结论不变。）

八、常见错误

误区	纠正
认为"能设计出更快的比较排序"	做不到。下界 $\Omega(n \log n)$ 对所有比较排序成立，无论怎么设计。
混淆"下界"与"实际复杂度"	下界是及格线。冒泡排序是 $O(n^2)$，远没达到下界；归并排序 $O(n \log n)$ 达到了。
认为 $O(n \log n)$ "还不够快"	它是理论最优。同量级下能比的只有常数和性质（稳定性、额外空间）。
以为下界也约束非比较排序	不约束。计数/基数排序跳出比较模型，可以做到 $O(n)$。
认为计数排序"更好"所以应该常用	它要求值域有限且不大。值域是 $2^{32}$ 时，计数数组要 4 GB。适用性差得多。
认为"达到下界"就是最优实现	达到下界只是第一步。常数优化（缓存、分支预测）同样重要 —— 理论 18.5ms 下界的任务，实际可能跑几百毫秒。

九、本节总结

决策树模型：每次比较是一个"是/否"提问，整个排序过程是一棵二叉树。$n$ 个元素有 $n!$ 种排列，所以树至少需要 $n!$ 个叶子。
下界推导：深度为 $k$ 的二叉树最多 $2^k$ 个叶子，故 $2^k \ge n!$，即 $k \ge \log_2(n!)$。
数值：$n = 30$ 时有 $30! \approx 2.65 \times 10^{32}$ 种排列，但只需 108 次比较就能区分。
近似公式：$\log_2(n!) \approx n \log_2 n - 1.4427n$。实测最后一列稳定在 $\log_2 e = 1.4427$。
$O(n \log n)$ 是理论最优，不是"还不错的成绩"。快排、归并、堆排都到顶了。
下界不等于可达：小 $n$ 时能做到，大 $n$ 时"达到下界"的算法极难写且常数巨大。工程上追求"达到量级 + 常数小"。
突破下界只能靠"不比较"：计数排序、基数排序利用元素的值本身，跳出比较模型。代价是适用性变窄。

本章小结：第 7 章从"最土的三种排序"出发，走到了一个相当深刻的理论结论。

7.1 三种 $O(n^2)$ 排序的"性格"完全不同 —— 实测随机输入下最快的是最慢的 4 倍，近乎有序时差 150 倍。
7.2 稳定性：一个"相等时怎么办"的约定，决定了多关键字排序能否成立。
7.3 逆序对：把"数组有多乱"变成一个精确的数字，并证明它恰好等于冒泡的交换次数。
7.4 下界：用一个朴素到几乎不需要数学的计数论证，证明了 $O(n \log n)$ 是任何比较排序都突破不了的天花板。

下一章衔接：既然天花板是 $n \log n$，那第 8 章的任务就很明确了 —— 看几种达到这个量级的排序算法，比较它们的常数、稳定性和适用场景。第一个是归并排序：它最"老实"，任何输入都是 $O(n \log n)$，而且是稳定的。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "7.4",
  "title": "下界：为什么比较排序绕不开 n log n",
  "covered": [
    "决策树模型与「n! 种排列需要 n! 个叶子」的观察",
    "下界推导 2^k >= n! => k >= log2(n!)",
    "n! 的增长实测（n=50 时 3x10^64）与 log 后的温和增长",
    "log2(n!) vs n*log2(n) 的差距实测（稳定在 1.4427n = log2(e)）",
    "「下界是及格线不是所有人都在及格线上」的澄清",
    "下界不等于可达（小 n 的实际最优比较次数）",
    "跳出比较模型：计数排序/基数排序的预告",
    "下界证明的完整五步写法",
    "三路比较不改变量级结论"
  ],
  "unresolved": [
    "归并排序留到 8.1",
    "计数排序与基数排序留到 8.4",
    "工业级排序（内省排序）留到 8.5"
  ],
  "canonical_terms": {
    "决策树": "把排序算法的比较过程表示为二叉树，内部节点是比较、叶子是输出",
    "下界": "任何算法都不可能低于的复杂度下限",
    "比较排序": "只通过比较元素大小来决定顺序的排序算法",
    "非比较排序": "利用元素值本身的信息、不依赖比较的排序算法"
  },
  "symbols_units": {
    "n!": "n 个元素的全排列数",
    "log2(n!)": "比较排序的比较次数下界",
    "log2(e)": "约 1.4427，log2(n!) 与 n*log2(n) 的系数差"
  },
  "assumptions": [
    "读者已掌握 7.3 的比较模型与 1.2 的对数",
    "读者理解二叉树的深度与叶子的关系"
  ],
  "word_count_actual": 3020,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch07/Sec74/",
    "log2(n!) 与 n*log2(n) 的差距实测逐项核对（最后一列收敛到 1.4427）",
    "n! 的精确值用 BigInteger 计算",
    "练习 7.4.1 的估算已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "next": "8.1 归并排序：稳定且可预测"
}

7.4　下界：为什么比较排序绕不开 n \log n