quick sort的时间复杂度的定量分析

Post author:admin
Post published:2014年5月15日
Post category:IT
Post comments:0评论

对quick sort算法的复杂度做一下更精确的分析。

quick sort是典型的divide-and-conquer算法。算法描述如下：

从待排序数组中选取一个作为pivot
用pivot把待排序数组分成两部分，使得一部分大于pivot，一部分小于pivot。
对这两个子数组分别递归调用此算法

示例代码：选取数组的第一个元素做pivot。

template <typename Iterator>
void quick_sort_with_std_partition(Iterator begin, Iterator end) {
  auto len = end - begin;
  if (len <= 1) return;
  auto p = *begin;
  typedef decltype(p) T;
  Iterator iter = std::partition(
      begin + 1, end,
      [&p](const T & d)->bool { return p>=d; });
  std::iter_swap(iter - 1, begin);
  quick_sort_with_std_partition(begin, iter - 1);
  quick_sort_with_std_partition(iter, end);
}

基本上是个程序员都知道quick sort的平均时间复杂度为O(nlogn)，最坏为O(n^2)。昨天我又重新看了一下Hoare在1962发的那篇关于quick sort的论文，下面对quick sort所需的比较次数做一下精确分析。

假设我们选取的pivot恰好是这个数组的第k大元素的概率是$p_k$,那么quick sort所需要的平均比较次数为

$$ Q_n=n-1+\sum_{k=1}^n{p_k * (Q_{k-1} + Q_{n-k})} $$

随机化的quick sort

继续假设pivot是从输入的数组均匀随机选取的，那么有$p_k=1/n$

$$ Q_n=n-1+\sum_{k=1}^n{\frac{Q_{k-1}}{n}} + \sum_{k=1}^n{\frac{Q_{n-k}}{n}} = n-1+\frac{2}{n}\sum_{k=1}^n{Q_{k-1}} =2(n+1)\sum_{k=1}^n{\frac{1}{k}}-4n = 2n\ln{n} + (2\gamma-4)n+2\ln{n}+O(1) $$ 其中$ \gamma $是Euler-Mascheroni常量，约等于0.5772….http://mathworld.wolfram.com/Euler-MascheroniConstant.html