快速排序算法复杂度分析

发表于 更新于 阅读次数： Disqus： 本文字数： 830 阅读时长 ≈ 3 分钟

大家都知道快排的时间复杂度是O(n*ln[n])，那么这个复杂度是如何计算出来的呢？

以下是快排的java算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class QuickSort {
    public static void quickSort(int a[], int start, int end) {
        if (start >= 0 && end <= a.length - 1 && start < end) {
            int low = start;
            int high = end;
            int splitKey = a[start];
            while (start < end) {
                while (start < end && a[end] >= splitKey) end--;
                a[start] = a[end];
                while (start < end && a[start] <= splitKey) start++;
                a[end] = a[start];
            }
            a[end] = splitKey;
            quickSort(a, low, start - 1);
            quickSort(a, start + 1, high);
        }
    }

    public static void quickSort(int a[]) {
        quickSort(a, 0, a.length - 1);
    }
}

最好的情况下，每次划分对一个记录定位后，要记录的左侧子序列与右侧子序列的长度相同。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，所需的时间为O(n)。

证明如下：

设\(T_n\)是对n个记录的序列进行排序的时间，每次划分后，正好把划分区域分为长度相等的2个子序列，显然\(T(0)=T(1) =1\),则有：

\[ \begin{equation} \begin{split} T(n)&=2T(n/2)+n \\ &=2(2(T(\frac{n}{4})+\frac{n}2))\\ &=...\\ &=nT_1+nlog_2n=O(n*ln[n]) \end{split} \end{equation} \] 最坏的情况下，待排序的记录序列正序或逆序，每次划分只能得到一个比上一次划分少一个记录的子序列，（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i趟划分需要经过n-i次比较才能找个才能找到第i个记录的位置，因此时间复杂度为

\[ \sum^{n-1}_{i=1}(n-i)=\frac{1}{2}*n*(n-1)=O(n^2) \]

平均情况下，设轴值记录的关键码第k小（1≤k≤n）,则有： \[ \begin{equation}\begin{split}T(n) &= \frac {1} {n}\sum_{k=1}^{n}(T(n-k) + T(k-1)) +n \\ &=\frac{2}{n}\sum_{k=0}^{n-1}T(K)+n \end{split} \end{equation} \]

由上式可推出如下两式：

\[ n*T(n)=2\sum^{n-1}_{k=0}+n^2 \]

\[ (n-1)*T(n-1)=2\sum^{n-2}_{k=0}k+(n-1)^2 \]

两式相减,然后两边同除以n(n+1)得 \[ \begin{equation} \frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2n-1}{n(n+1)} \end{equation} \] 令\(B_n=\frac{T(n)}{n+1}\)

则\(B_0=\frac{T(0)}{1}=1\)

所以: \[ \begin{align} B_n-B{n-1} = (2n-1)(\frac{1}{n}-\frac{1}{n+1}) \\ B_{n-1}-B{n-2} = (2n-3)(\frac{1}{n-1}-\frac{1}{n}) \end{align} \]

累加得： \[ \begin{equation}\begin{split} B_n&=-\frac{2n-1}{n+1}+\frac{2}{n}+\frac{2}{n-1}+...+\frac{2}{2} \\ &=-\frac{2n-1}{n+1}+2(\frac{1}{n}+\frac{1}{n-1}+...+\frac{1}{2}) \end{split}\end{equation} \] 由于k>2时，\(\frac{1}{k}<ln[\frac{k}{k-1}]\)，所以：

\[ \frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}<ln[\frac{2}{1}]+ln[\frac{3}{2}]+...+ln[\frac{n}{n-1}]=ln[n] \] 所以 \[ f(n)=ln[n]-(\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})>0 \] 又因为f(n)单调递减，单调有界数列极限定理，所以f(n)有界

\[ \begin{equation}\begin{split} &lim_{n->∞}1-f(n)\\ &=1+ \frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}-ln[n]\\ &≈0.57721566490153286060651209 \end{split} \end{equation} \]

此数称为欧拉常数，

约为 0.57721566490153286060651209

所以

\[ \begin{equation} B_n=-\frac{2n-1}{n+1} + ({γ}+ln[n]-1)*2 \end{equation} \]

所以

\[ \begin{equation}\begin{split} T(n)&=-2n+1+(n+1)*(γ+ln[n]-1)*2\\ & = O(n*ln[n]) \end{split} \end{equation} \]

如果有何处不当，请不吝赐教，一定多加完善。谢谢

参考资料：

【1】《算法设计与分析》第二版 王红梅