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

  • Post author:
  • 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

用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

This article is from:https://www.sunchangming.com/blog/post/4625.html

发表评论