排序下界定理

概述

排序下界定理（Sorting Lower Bound Theorem）：任何基于比较的排序算法，在最坏情况下至少需要 $\Omega (n\log n)$ 次比较才能对 $n$ 个元素排序。该定理通过决策树模型建立，证明了 归并排序 和 快速排序（期望情况）的 $\Theta (n\log n)$ 复杂度已经是渐近最优的。

定理陈述

形式化陈述

定理：在最坏情况下，任何基于比较的排序算法对 $n$ 个元素进行排序至少需要 $\Omega (n\log n)$ 次比较。形式化地：

$T_{\text{worst}}(n)\ge \lceil \lg (n!)\rceil =\Omega (n\log n)$

其中 $n!$ 是 $n$ 个元素的所有排列数，$\lg$ 表示以 2 为底的对数。

“基于比较的排序”：算法仅通过比较两个元素的大小关系（$<$、$=$、$>$）来获取输入信息，不利用元素的其他性质（如数值范围、位数等）。

证明概要

证明思路

证明通过将比较排序算法建模为决策树（decision tree），然后利用决策树的结构性质推导下界。

步骤 1：建立决策树模型

对一个固定的比较排序算法 $A$ 和固定的输入大小 $n$，将 $A$ 在所有可能的 $n!$ 种输入排列上的执行过程建模为一棵决策树 $T_A$：

• 每个内部节点表示一次比较操作 $a_i:a_j$（比较第 $i$ 个和第 $j$ 个元素）
• 每个内部节点有 3 个子节点（分别对应 $<$、$=$、$>$ 三种结果；若假设所有元素互不相同，则为 2 个子节点）
• 每个叶节点对应一种排列（排序结果）
• 从根到叶的路径长度 = 该输入所需的比较次数

步骤 2：决策树的基本性质

• $T_A$ 至少有 $n!$ 个叶节点（每种输入排列至少对应一个不同的叶节点，因为排序结果不同）
• $T_A$ 是一棵合法的比较树（每个内部节点度数至多为 3；假设元素互异时度数为 2）

步骤 3：叶节点数与树高的关系

设 $T_A$ 的高度为 $h$（即最长根到叶路径的长度）。一棵高度为 $h$ 的二叉树最多有 $2^h$ 个叶节点。因此：

$n!\le \text{叶节点数}\le 2^h$

两边取对数：

$h\ge \lg (n!)$

步骤 4：Stirling 公式估计

利用 Stirling 公式的下界：

$n!>{\left(\frac{n}{e}\right)}^n$

因此：

$\lg (n!)>\lg {\left(\frac{n}{e}\right)}^n=n\lg \left(\frac{n}{e}\right)=n\lg n-n\lg e=\Omega (n\log n)$

更精确地，Stirling 公式给出：

$\lg (n!)=n\lg n-n\lg e+O(\lg n)$

因此 $h\ge \lg (n!)=\Omega (n\log n)$。

步骤 5：结论

决策树的高度 $h$ 等于算法在最坏情况下所需的比较次数。因此任何基于比较的排序算法的最坏情况比较次数至少为 $\Omega (n\log n)$。

学术参考：UNL CSE423 课程讲义包含决策树证明的完整推导：http://www.cs.nthu.edu.tw/~wkhon/algo08-lectures/lecture7.pdf

关键推论

• 归并排序和堆排序是渐近最优的：它们的最坏情况时间复杂度为 $O(n\log n)$，与下界 $\Omega (n\log n)$ 匹配，因此是 $\Theta (n\log n)$，达到最优
• 快速排序的期望最优性：随机化快速排序的期望比较次数为 $O(n\log n)$，在期望意义下也是最优的
• 突破下界的途径：若要突破 $\Omega (n\log n)$ 下界，必须使用非比较的排序方法，如：
  • 计数排序：$O(n+k)$，其中 $k$ 是数值范围
  • 基数排序：$O(d(n+k))$，其中 $d$ 是数字位数
  • 桶排序：$O(n)$ 期望时间（假设输入均匀分布）

应用场景

• 算法导论 Ch8：排序下界定理是比较排序算法复杂度分析的基石
• 算法设计指导：在设计新的排序算法时，该定理告诉我们比较排序不可能突破 $O(n\log n)$，若需要更快的排序，必须利用输入的特殊性质
• 算法比较基准：为比较不同排序算法的优劣提供了理论基准线
• 计算复杂性理论：决策树模型是计算复杂性分析的重要工具，排序下界是其经典应用

参见

• 归并排序 — 达到 $\Theta (n\log n)$ 下界的稳定排序算法
• 快速排序 — 期望 $\Theta (n\log n)$ 的原地排序算法
• 分治法 — 归并排序和快速排序的设计策略