算法篇——比较排序算法的下界

16 October 2013

无论是插入排序还是归并排序、快速排序，都是建立在比较排序方法上，即通过比较排序。我们来看看一个简单的过程，假设存在三个数字a1，a2，a3：

                     a1 < a2?
                    /        \
            a1 < a3?          a2 < a3?
           /       \         /        \
      a2 < a3?   [2 1 3] a1 < a3?   [1 2 3]
     /       \          /        \ 
   [3 2 1]  [2 3 1]   [3 1 2]   [1 3 2]

方法很简单，如果a1小于a2，比较a1与a3的大小，如果a1大于a3，则排序结果是[2 1 3]，后同。如果有n个数，将会有n!种可能的排序结果。而最坏的比较次数如图将是3，即这棵二叉树的深度，假设是d。

事实上，一棵二叉树，最多含有2^d(2的d次方，^表示做指数，后同)个叶节点，所以：

n! ≤ 2^d。

两边取对数，得到：

d ≥ log(n!)

这里对数以2为底数。这时也许你会说，我们找到比较排序的下界了，是log(n!)。事实上，这并不能算一个严格下界。我们需要对log(n!)继续处理。

《算法导论》中的3.18公式明确给出:

log(n!) = Θ(nlogn)

证明方法除了使用Stirling公式以外，可以如下证明：

log(n!) = log1 + ... + logn ≥ n/2 * log(n/2) = n/2 * logn - n/2 = c1 * logn
log(n!) = log1 + ... + logn ≤ nlogn = c2 * logn

于是我们得到上式。由于底2的对数是递增函数，则d ≥ Ω(nlogn)。所以nlogn才是比较排序的上界。堆排序和归并排序都可以达到这个下界。

当然，在一些特殊情况下，能够达到比这个下界还好的时间复杂度，不过对于一般情况，下界便是nlogn。

到这里，也许你会有所疑问，有没有方法能够把这个下界再提高一点。那当然就要靠你的聪明才智了！较为常见的复杂度还有n^a，b^n次方等（a，b均为某常数），想办法向其靠拢吧。

这就是为什么归并排序这么快，因为它已经达到最好的情况（一般情况）了！

参考材料：

algorithm 5

algorithm 5