比较排序算法决策树中叶节点的最大可能深度是多少？

核心结论 #

我们默认讨论无冗余比较的合法比较排序决策树（无重复无意义比较）：

• 最优比较排序的最坏情况叶节点深度下界为 ceil(log₂(n!))，等价于 Ω(n log n)
• 无冗余比较排序的叶节点最大可能深度为 n(n-1)/2
• 若允许冗余比较，理论上叶节点深度可以无限大（无实际工程价值）

推导依据 #

1. 决策树构造规则 #

比较排序的决策树是一棵二叉树：

• 每个内部节点对应一次元素比较操作，格式为 a[i] < a[j]
• 左子树对应比较结果为真的执行分支，右子树对应比较结果为假的执行分支
• 每个叶节点对应输入序列的一个合法排列，也就是最终排序结果
  长度为n的输入序列共有 n! 种不同排列，因此决策树至少包含 n! 个叶节点才能覆盖所有排序结果。

2. 深度下界推导（最优排序场景） #

二叉树的叶节点数量和深度有明确的约束关系：深度为h的二叉树最多有 2^h 个叶节点。
我们需要 2^h ≥ n!，两边取对数可得 h ≥ log₂(n!)，根据斯特林公式近似，log₂(n!) ≈ n log₂n - n log₂e，也就是等价于 Ω(n log n)，这也是比较排序最坏时间复杂度的理论下界，归并排序、堆排序等最优比较排序的最坏情况复杂度刚好符合这个下界。

3. 最大深度推导（无冗余排序场景） #

n个元素的全序关系一共包含 C(n,2) = n(n-1)/2 个两两大小关系对。如果比较排序算法每次比较只能获得一对元素的大小关系，没有通过传递性获得额外的序信息（比如完全逆序输入下的冒泡排序、插入排序），那么需要做完所有 n(n-1)/2 次比较才能确定最终的全序排列，此时对应的叶节点深度就是 n(n-1)/2，对应算法的最坏时间复杂度为 O(n²)。 #

内容的提问来源于stack exchange，提问作者jade