0%

QuickSort 快速排序时间复杂度的推导与证明

QuickSort 快速排序时间复杂度的推导与证明

1 算法的描述

快排的主要思想来源于分治法.下面是快排应用分治法的主要步骤:

  • 分解: 将原数组A[p..r]原址划分为两个子数组A[p...q-1]和A[q+1..r],使得数组A[p...q-1]中的元素都小于数组A[q+1..r]中的元素.

  • 解决: 通过递归调用完成对A[p...q-1]和A[q+1...r]的快速排序.

  • 合并: 由于快排是原址排序算法,因此不需要合并操作,数组A[p...r]已经有序

下面给出QuickSort的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
QUICKSORT(A,p,r)
if p < r
q = PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)

PARTITION(A,p,r)
x=A[r]
i=p-1
for j=p to r-1
if A[j] <= x
i++;
swap A[i] and A[j]
swap A[i+1] and A[j]
return i+1

本文从最好时间复杂度、最差时间复杂度、平均时间复杂度三个方面进行算法时间复杂度的推导与分析。

下文若无特殊说明,将QuickSort过程的时间复杂度用\(T(n)\)表示。

2 时间复杂度的分析

从QuickSort的伪代码可知,该算法的时间复杂度主要取决于第3行PARTITION过程取得的划分是否平衡。如果取得的划分是平衡的,那么快速排序的性能接近于归并排序;如果取得的划分是不平衡的,那么快速排序的性能接近于插入排序。

2.1 最差时间复杂度的推导

什么时候算法会产生产生最差的时间复杂度呢?划分及其不平衡的时候。

那么什么是及其不平衡的划分呢?这个问题其实很简单,当上述PARTITION过程分别产生了规模为\(n - 1\)\(0\)划分的时候。注意,在PARTITION过程产生划分的过程中,实际上是产生了一个“主元”(对应于代码第8行的变量x),然后PARTITION过程以该主元为中心划分数据,也就是说,在计算划分的规模的时候,不将主元计算在内,因此上述规模为\(n - 1\)\(0\)划分不包括主元。

那么可以得到这个时间复杂度公式:

\[ T(n)=T(n-1)+T(0)+T_{partition}(n)\tag{1} \]

其中\(T(n-1)\)\(T(n)\)分别是递归处理规模为\(n-1\)\(0\)的子划分的表达式,\(T_{partition} (n)\)是PARTITION过程的时间复杂度。由于PARTITION过程的执行时间只与n有关且与n成正比,因此\(T_{partition} (n) = \theta(n)\)(其中\(n = r - p\))。

为什么 n = r - p 而不是 n = r - p + 1? 因为主元不计算在内!

再经过进一步的观察可以得知,对于QuickSort过程,当\(p \geq r\)时(也即\(n = r - p = 0\)时)整个过程会直接返回,此时时间复杂度为0,因此\(T(0) = 0\)

根据以上讨论可以将公式(1)简化为下面的样子:

\[ T(n) = T(n - 1) + \theta(n) \tag{2} \]

用代入展开法求解该递归表达式,可得:

$$ \[\begin{align*} T(n) = T(n - 1) + \theta(n) \\ = T(n - 2) + 2\theta(n) \\ = ... = T(0) + n\theta(n) \\ =\theta(n^2) \tag{3} \\ \end{align*}\] $$

最终得知快速排序的最差时间复杂度为:

\[ T(n) = \theta(n^2) \]

该时间复杂度只有在QuickSort的每一次递归调用都产生一个最不平衡的划分时才会出现。

2.2 最好时间复杂度的推导

既然最差情况是产生最不平衡的划分的情况,那么最好情况自然而然就是划分得到最平衡的划分的情况。

在这种情况下,原问题被划分出两个规模分别为\(\lfloor \frac{n}{2} \rfloor\)\(\lceil \frac{n}{2} \rceil - 1\)的两部分。自然,这种情况可以直接写出QuickSort过程的时间复杂度: \[ T(n) = T(\lfloor \frac{n}{2} \rfloor) + T(\lceil \frac{n}{2} \rceil - 1) + \theta(n) \]

这里忽略掉取整符号和常数项,得:

\[ T(n) = 2T(\frac{n}{2}) + \theta(n) \]

应用主方法求解该递推公式:

主方法是指利用主定理来解决递归式的方法。

主定理: 令\(a \geq 1\)\(b>1\)是常数,\(f(n)\)是一个函数,T(n)是定义在非负整数上的递归式: \[ T(n) = af(\frac{n}{b}) + f(n) \tag{4} \] 其中我们将\(\frac{n}{b}\)解释为\(\lfloor \frac{n}{b} \rfloor\)\(\lceil \frac{n}{b} \rceil\)。那么\(T(n)\)有如下渐进界:

  1. 若对某个常数\(\epsilon > 0\),有\(f(n) = O(n^{log_{b}a-\epsilon})\),则\(T(n) = \theta(n^{log_{b}a})\).
  2. \(f(n) = \theta(n^{log_{b}a})\),则\(T(n) = \theta(n^{log_{b}a} lgn)\)
  3. 若对某个常数\(\epsilon > 0\),有\(f(n) = \Omega(n^{log_{b}a+\epsilon})\),且对某个常数\(c<1\)和所有足够大的n有\(af(\frac{n}{b}) \leq cf(n)\),则\(T(n) = \theta(f(n))\)

易知\(a = 2, b = 2, f(n) = n\), 于是符合主方法的第二种情况,可得\(T(n) = \theta(n^{log_{b}a}lg n) = \theta(nlg n)\).

2.3 平均情况下时间复杂度的推导

平均情况下产生的划分同时混合有"好"和"差"的划分,其中好的和差的划分是随机出现在递归树的各层。基于直觉,假设平均情况下"好"的和"差"的划分是交替出现的,且好的划分是最好划分,差的划分是最差划分。下图说明了这种划分。

1
2
3
4
5
     n            \
/ \ |-->θ(n)
0 n-1 /
/ \
(n-1)/2-1 (n-1)/2

在这种情况下,根节点(规模为n)产生了一个"差"的划分,规模分别为0和n-1.其中规模为n-1的划分产生了一个好的子划分,规模分别为\(\frac{(n-1)}{2}-1\)\(\frac{(n-1)}{2}\)。此种情况下,进行第一次划分的时间代价为\(\theta(n)\),进行第二次划分的时间代价为\(\theta(n-1)\),这两次代价之和为\(\theta(n) + \theta(n-1) = \theta(n)\)(忽略掉常数项),这与直接在第一次划分出最高情况的时间代价是一样的(都是\(\theta(n)\)!,见下图),划分出的结果也相同:都划分出了规模分别为\(\frac{(n-1)}{2}-1\)\(\frac{(n-1)}{2}\)的划分(这里忽略规模为0的划分,因为该划分时间复杂度为0) .因此这种情况下的时间复杂度为\(O(nlgn)\)。使用\(O\)符号而不使用\(\theta\)符号的原因在于此种情况的时间复杂度常数因子要大一些。

1
2
3
         n            \
/ \ |-->θ(n)
(n-1)/2-1 (n-1)/2 /

3 时间复杂度的详细证明

虽然我很不想这么说,但是证明该算法时间复杂度比较枯燥,且需要一定的数学功底。如果你对详细证明不感兴趣,或者对于这一块数学不熟悉,那就跳过本节吧!

证明过程中需要用到的数学知识:

  1. 求导(一重导数和二重导数),级值&最值求解
  2. 级数求和(主要是调和级数)
  3. 一点概率论知识

3.1 最坏情况

在前面的叙述中,能够得知最坏情况的时间复杂度为\(O(n^2)\)。下面来证明这一点。

因为此时需要的是最坏情况的划分,因此可以得到一下递归表达式:

$$ \[\begin{align*} T(n) = \begin{cases} \max_{0 \leq q \leq n-1}(T(q) + T(n - q - 1)) + \theta(n) \tag{5} &,n \neq 0 \\ 0&,n=0 \end{cases} \end{align*}\] $$

因为其中两个划分的规模之和为\((q) + (n - q - 1) = n - 1\)(因为主元不计算在内),所以q变化的范围是\([0,n-1]\)

max函数的意义是求当时间复杂度最高时q的值(也即最坏情况)。

不妨猜测\(T(n) \leq cn^2\)成立,下面来证明这一点。

I. 首先考虑\(n=0\)的情况,此时\(T(0)=0\)\(T(0) \leq cn^2 = 0\)成立。

  1. 考虑\(n \neq 0\)的情况。假设\(T(n) \leq cn^2\)成立, 那么 \[ \max_{0 \leq q \leq n-1}(T(q) + T(n - q - 1)) + \theta(n) \\ \leq \max_{0 \leq q \leq n-1}(cq^2 + c(n - q - 1)^2) + \theta(n) \\ = c\max_{0 \leq q \leq n-1}(q^2 + (n - q - 1)^2) + \theta(n), \]

其中令\(f(q) = q^2 + (n - q - 1)^2\),解得其在\(q \in [0,n-1]\)区间的最大值是\((n-1)^2\)(在端点0或n-1处取到)。

因此 \[ c\max_{0 \leq q \leq n-1}(q^2 + (n - q - 1)^2) + \theta(n) \\ \leq c(n-1)^2 + \theta(n) \leq cn^2 \] 证毕。

3.2 最好情况

最好情况的证明过程类似于最坏情况的证明,区别在于原式的max改为min,这里不再赘述。

3.3 平均情况期望运行时间

下面的论证假设源数组中的元素各异,且呈随机排列。

仔细观察QuickSort的代码可以得知,QuickSort的运行时间是由PARTITION操作的运行时间决定的。由于每执行一次PARTITION操作就会选出一个主元,且这个主元不会包含在后续QuickSort和PARTITION过程的调用中,因此PARTITION过程至多会被调用n次。那么,已经知道了第3行PARTITION过程至多会被调用n次,在每一次调用PARTITION的过程都包括一些固定的工作量和执行若干次for循环。因此,若若伪代码中第11行被调用了X次,那么整个QuickSort算法的时间复杂度就是\(O(n+X)\)

为了便于分析,假设将原数组各个元素按升序排列并重新命名为\(z_1,z_2,...,z_n\),定义\(Z_{ij}\)为下标位于\(i \in [i,j]\)的所有元素的集合,也即\(Z_{ij}=\{z_i,z_{i+1},...,z_{j}\}\)

定义随机变量\(X_{ij}=I\{z_i与z_j进行比较\}\)。由于各个元素只与主元进行比较,而在某一次PARTITION过程结束之后,该主元就不会被比较了。因此对于任何一对元素\(z_i\)\(z_j\)来说只会进行一次比较。

因此总的比较次数如下表达式所示: \[ X = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij} \tag{6} \] 两边取期望,得: \[ E(X)=E[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}E[X_{ij}]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}P\{z_i与z_j进行比较\} \] 由于每一对元素仅会被比较一次,在某一次调用PARTITION的过程中,某一对元素会被比较仅仅会发生在这一对元素中的某个元素是主元的时候。同时注意到,如果在\(z_i\)\(z_j\)之间的某个位置被选为了主元,那么\(z_i\)\(z_j\)就不可能被比较了。因此,对于某一次PARTITION过程来说,\(z_i\)\(z_j\)会进行比较,当且仅当\(Z_{ij}\)被选为主元的第一个元素是\(z_i\)\(z_j\)。(注:这里的第一个对与集合\(Z_{ij}\)而言的)

同时注意到,\(Z_{ij}\)中的元素都是等可能地被选为主元,且\(Z_{ij}\)中有\(j-i+1\)个元素,因此任何元素被选为主元地概率都是\(\frac{1}{j-i+1}\)

于是, \[ P\{z_i与z_j进行比较\} = P\{z_i或z_j是集合Z_{ij}选出的第一个主元\} \\ =P\{z_i是集合Z_{ij}选出的第一个主元\} + P\{z_j是集合Z_{ij}选出的第一个主元\} =\frac{2}{j-i+1} \] 于是原期望为: \[ E(X)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1} \]\(k=j-i\),得 \[ E(X)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1} = \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1} < \sum_{i=1}^{n-1}\sum_{k=1}^{n}\frac{2}{k} = \sum_{i=1}^{n-1}O(lgn)=O(nlgn) \] 因此,在元素各异的情况下,QuickSort的期望运行时间为\(O(nlgn)\)

4 参考

本文章的论述过程主要参考《算法导论》第七章:快速排序的思路来证明。