基于比较的排序算法的时间复杂度下界证明 题目描述 我们都知道，像快速排序、归并排序和堆排序这样的基于比较的排序算法，其平均或最坏情况下的时间复杂度为 O(n log n)。现在，请你证明：任何基于比较的排序算法在最坏情况下都需要至少 Ω(n log n) 次比较。换句话说，O(n log n) 是基于比较的排序算法无法突破的一个“下界”。 解题过程 理解问题核心 我们需要证明，只要排序算法是通过“比较”元素来决策的（即每次操作只能问“元素A是否小于元素B？”），那么在最坏情况下，它必须进行至少与 n log n 成正比次数的比较才能保证正确排序。这个证明不针对某个具体算法，而是适用于所有可能的基于比较的算法。 引入决策树模型 任何基于比较的排序算法都可以用一棵 决策树 来表示： 每个 内部节点 代表一次比较（例如“aᵢ < aⱼ?”）。 每个 叶节点 代表算法最终确定的一种输入序列的排序结果（一种排列）。 从根到叶的路径表示算法根据比较结果一步步决策的过程。 分析决策树的性质 对于 n 个元素，可能的排序结果有 n! 种（即所有排列的数量）。 由于算法必须能区分所有可能的排列，决策树必须至少有 n! 个叶节点 （每个叶对应一种正确的排序结果）。 一棵高度为 h 的二叉树最多有 2ʰ 个叶节点。因此，为了容纳 n ! 个叶节点，树的高度 h 必须满足： 2ʰ ≥ n! 这意味着 h ≥ log₂(n!) 。 计算下界 最坏情况下的比较次数就是树的高度 h，所以我们需要估算 log₂(n !) 的大小。 利用斯特林公式（Stirling's approximation）： n! ≈ √(2πn) × (n/e)ⁿ 取对数后： log₂(n!) ≈ n log₂ n - n log₂ e + O(log n) 其中 n log₂ n 是主导项，因此 log₂(n!) = Ω(n log n) 。 严谨推导 即使不用斯特林公式，我们也可以直接证明： log₂(n !) = log₂ 1 + log₂ 2 + ... + log₂ n 利用积分上下界： ∫₁ⁿ log₂ x dx ≤ log₂(n !) ≤ ∫₁ⁿ⁺¹ log₂ x dx 计算得： n log₂ n - n log₂ e ≤ log₂(n!) ≤ (n+1) log₂(n+1) - n log₂ e 因此 log₂(n!) = Θ(n log n) ，即 h = Ω(n log n) 。 结论 由于任何基于比较的排序算法的决策树高度必须至少为 log₂(n !) = Ω(n log n)，所以最坏情况下的比较次数不可能低于 Ω(n log n)。这就是为什么归并排序和堆排序等算法是渐近最优的——它们达到了这个下界。 总结 这个证明的关键在于将算法抽象为决策树，并通过排列数量和二叉树大小的关系，推导出比较次数的下界。它解释了为什么 O(n log n) 是比较排序的“天花板”，而像桶排序或基数排序能突破它，是因为它们利用了元素本身的特性（如整数范围），而非仅仅依赖比较。