基于比较的排序算法时间复杂度下限

昨天和74LS138学长聊天的时候,突然想到一个问题:

基于比较的排序算法中,有很多可以达到\(O\left( {n\log n} \right)\)的时间复杂度,但是能不能找到一种在时间复杂度意义上更快速的排序算法?

在网上查了一下,答案是不能,而且竟然可以很简单地证明出这个结论。

\(n\)个数顺序的可能情况一共有\(n!\)种,如果把每种情况当做二叉树的一个叶子结点,那么每一次比较判断就相当于在二叉树的分叉处选择一个分支,一次排序就可以看做从根节点到一个叶子结点的路径。

根据叶子结点有\(n!\)个可以得出二叉树的高度至少为\(\log _2 \left(n! \right)+1\),也就是说至少存在一种情况使得需要比较\(\log _2 \left(n! \right)\)次。

根据Stirling公式(\(n!\sim\sqrt {2\pi n} {\left( {\frac{n}{e}} \right)^n}\))近似,可以得出基于比较的排序算法时间复杂度下限为\(O\left( {n\log n} \right)\)。

 

《基于比较的排序算法时间复杂度下限》有8个想法

  1. 这是平均复杂度下限。实际中排序操作不与比较操作一一对应,也就是有可能复杂度不及nlog(n)或者远大于nlogn。对于随机优化简单快速排序,总有可能会产生实际代价为O(n^2)的排序过称(每次都恰好没有二分)。对于插入排序(完全依赖比较),最好的情况为n。但博主的证明似乎表示最优复杂度不低于nlogn。这点似乎有问题。请注意。当然Quicksort 太过时了。标准库都用Introsort了(我喜欢叫它复合排序)

    1. 最好情况不能代表算法的时间复杂度。74LS138学长说根据平摊分析,平均情况与最坏情况应该是一样的。

      1. 我说的有问题。对于快排,平均情况比最坏情况下的复杂度低阶。我来给一个粗糙的平摊分析,仅供参考:
        T(n) = Tp(n) + T(k) + T(n – k – 1)
        其中k为枢轴左侧元素个数,T(n)为将n个元素快排的时间,Tp(n)是将n个元素partition的时间,满足:Tp(n)=Θ(n),取近似Tp(n) = C * n
        所以有:T(n) = C * n + T(k) + T(n – k – 1)
        此处均摊假定k服从0..n上的均匀分布,则:T(n) = C * n + Σ{T(k) + T(n – k – 1), k = 0..n} / (n + 1),代入T(n) = Θ(nlogn),等式成立
        所以:T(n) = Θ(nlogn)

    1. 我现在看到了。。这个是最坏的情形。可以证明有L片叶子的完全二叉树的叶子平均深度大于等于ceil(logL) 。这样就证明了平均的时间下界

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注