基于比较的排序算法的时间复杂度下界的证明

· · 算法·理论

希尔排序

基于比较的排序算法的时间复杂度下界的证明

引言

众所周知，在所有基于比较的排序算法中，最坏时间复杂度的下界是 O(n\log n) 不知道的现在知道了。

注意是最坏时间复杂度，否则有序数列我暴力插入 O(n) 秒了。

下面进行一个简单的证明，相信大家都能看懂看不懂的多看几遍。

决策树模型

首先，我们需要明确的是，基于比较的排序算法，核心操作就是比较两个元素的大小。每次比较都是一个二分结果，要么小于、要么不小于。换句话说，这些算法的所有决策都可以抽象为一个决策树：

显然，这个决策树必须覆盖输入的所有可能排列Bogosort：我没意见，才能得出排序的正确结果。

因此

对于 n 个元素，排列数是 n!。因此，决策树的叶子节点数至少为 n!，否则根本无法穷尽所有可能的排序结果。设决策树的高度为 h，那么树最多可以有 2^h 个叶子节点。因此，树的高度 h 必须满足：

2^h \geq n!

对两边取对数得到：

h \geq \log_2(n!)

这意味着，任何基于比较的排序算法最坏情况下至少需要 \log_2(n!) 次比较。

关于 \log_2(n!)

\texttt{Stirling} 公式

接下来，我们需要计算 \log_2(n!) 的量级。为此，我们使用斯大特林公式 \texttt{(Stirling's Approximation)}：

n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n

通过集中注意力，我们可以注意到：

\log(n!) \sim n \log n - n

可以看到，n \log_2(n) 是主项。这也就是为什么任何基于比较的排序算法最坏情况下都无法突破 O(n \log n) 的时间复杂度——因为要区分 n! 种排列，少于 O(n \log n) 次比较是不可能的。谁要是突破了发论文记得挂我个八作

结论

综上所述，我们已经严格证明了：基于比较的排序算法无法突破 O(n \log n) 的时间复杂度。这个下界并非算法设计上的瓶颈，而是由数学原理决定的。

完结撒花✿✿ヽ(°▽°)ノ✿✿