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

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

quick sort是典型的分治(divide-and-conquer)算法。算法描述如下:

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

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

template <typename Iterator>  
void quick_sort(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(begin, iter - 1);
  quick_sort(iter, end);
}

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

quick sort的效率与划分是否平衡息息相关。

假设我们选取的pivot恰好是这个数组的第k大元素, 那么由它划分而得到的两个子数组的长度分别为k-1和n-k。假设pivot是第k大的元素的概率是\(p_k\)。假设对n个元素进行quick sort所需要的平均比较次数为\(Q_n\),那么有

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

上式前面的n-1是指划分成两个子数组需要进行n-1次比较,后面是对不同的\(p_k\)计算数学期望。

随机取pivot的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

用median3取pivot的quick sort

下面考虑常见的median3优化。即,随机选取3个元素,以它们的中值作为pivot

那么,在这种情况下,我们选取的pivot恰好是这个数组的第k大元素的概率是\(p_k = \frac{6(k-1)(n-k)}{n(n-1)(n-2)}\)

代入前面的式子,求解得 \( Q_n = \frac{12}{7}n\ln{n}+O(n) \) 。所以就渐进复杂度粗略来看,比随机选取的方式要提高\(1-\frac{12/7}{2} \approx 14\% \)的效率。

--

参考: Hoare在1962年发表的原始论文:http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥