聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

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

2014-05-16 03:20 浏览: 1994805 次 我要评论(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 = 2nln{n} + (2gamma-4)n+2ln{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}nln{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



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复