快速排序时间复杂度

快排的时间复杂度计算有很多种方法,规范的有数学主定理公式进行证明。这里简单通俗讲下O(n*logn)复杂度是怎么得出的。

在最优情况下,快排的每次划分都很均匀,假设有n个关键字,完整的排序需要T(n)时间,则一次划分需要对整个数组进行扫描,做n次比较,然后将数组一分为2,各自还需要T(n/2)的时间。

于是就有了下面的不等式:

T(n)≤2T(n/2) +n,T(1)=0  
T(n)≤2(2T(n/4)+n/2) +n=4T(n/4)+2n
T(n)≤4(2T(n/8)+n/4) +2n=8T(n/8)+3n
……
T(n)≤nT(1)+(log2n)×n= O(nlogn)

也就是说,在最优的情况下,快速排序算法的时间复杂度为O(n*logn)
再来看看最坏的情况,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,另一个为空。
时间复杂度为:

(n-1)+(n-2)+...+1=n(n-1)/2= O(n2)

因此,如果关键字序列是大部分有序的情况,不推荐使用快排。

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×