概率论与数理统计 (Spring 2023)/Average-case analysis of QuickSort

快速排序（Quicksort）是由Tony Hoare发现的基于比较的（comparison-based）排序算法。该算法的伪代码描述如下（为方便起见，假设数组元素互不相同——更一般情况的分析易推广得到）：

 QSort(A): 输入A[1...n]是存有n个不同数字的数组
 if n>1 then
      pivot = A[1];
      将A中<pivot的元素存于数组L，将A中>pivot的元素存于数组R; \\保持内部元素之间相对顺序
      递归调用QSort(L)和QSort(R);

该伪代码描述省略了对数组的存取归并等具体实现的交代。可以不妨认为算法中的[math]\displaystyle{ L }[/math]和[math]\displaystyle{ R }[/math]其实就分别是原数组[math]\displaystyle{ A }[/math]的前半部分[math]\displaystyle{ A[1...i-1] }[/math]和后半部分[math]\displaystyle{ A[i...n] }[/math]，其中[math]\displaystyle{ i }[/math]表示pivot（“基准”、“轴点”、“分水岭”元素）在数组[math]\displaystyle{ A }[/math]中的序数，即pivot是数组[math]\displaystyle{ A }[/math]中第[math]\displaystyle{ i }[/math]小的数。

作为基于比较的排序算法，我们将算法进行的元素间的比较次数作为算法的复杂性度量。在最坏情况（worst-case）输入下，我们描述的“快速排序”算法所使用的比较次数可以达到[math]\displaystyle{ \Theta(n^2) }[/math]。而且有趣的是，这一[math]\displaystyle{ \Omega(n^2) }[/math]的复杂度下界是在输入数组是一个已排好序的数组时达到的：此时pivot会将数组[math]\displaystyle{ A }[/math]划分为大小极不平衡的子数组[math]\displaystyle{ L }[/math]和[math]\displaystyle{ R }[/math]，递归树也因此极不平衡，而算法使用的比较次数可因此达到[math]\displaystyle{ (n-1)+(n-2)+(n-3)+\cdots+1=\Omega(n^2) }[/math]。

现在我们来分析这一算法的平均情况（average-case）复杂度。

快速排序算法的平均复杂度分析 I（基于全期望法则）

令输入数组[math]\displaystyle{ A }[/math]为[math]\displaystyle{ n }[/math]个元素的均匀分布的随机排列。不难验证：上述快速排序算法使用的比较次数，仅与[math]\displaystyle{ A }[/math]中元素的相对大小有关、而与具体数值无关。因此，不妨假设[math]\displaystyle{ A }[/math]为[math]\displaystyle{ n }[/math]次对称群[math]\displaystyle{ \mathcal{S}_n }[/math]中均匀分布的随机[math]\displaystyle{ n }[/math]元排列。

令随机变量[math]\displaystyle{ X_n }[/math]表示在该随机输入[math]\displaystyle{ A }[/math]下，快速排序算法使用的总比较次数。同时令[math]\displaystyle{ t(n)=\mathbb{E}[X_n] }[/math]表示其期望。正如刚刚解释的，[math]\displaystyle{ t(n) }[/math]是良定义的，因为期望值[math]\displaystyle{ \mathbb{E}[X_n] }[/math]仅与[math]\displaystyle{ n }[/math]有关。

对[math]\displaystyle{ 1\le i\le n }[/math]，定义[math]\displaystyle{ B_i }[/math]为如下事件：

• pivot在数组[math]\displaystyle{ A }[/math]中是第[math]\displaystyle{ i }[/math]小的元素。

则[math]\displaystyle{ B_1,B_2,\ldots,B_n }[/math]构成了对所有情况（样本空间）的一个划分。且每个事件[math]\displaystyle{ B_i }[/math]发生的概率有：

[math]\displaystyle{ \Pr(B_i)=\frac{(n-1)!}{n!}=\frac{1}{n} }[/math].

这是因为事件[math]\displaystyle{ B_i }[/math]等价于一个均匀分布的随机排列[math]\displaystyle{ \pi:[n]\xrightarrow[\text{onto}]{\text{1-1}}[n] }[/math]有[math]\displaystyle{ \pi(1)=i }[/math]，而这件事的概率为[math]\displaystyle{ \frac{1}{n} }[/math]。

因此，根据全期望法则（law of total expectation），有：

[math]\displaystyle{ \begin{align} t(n) = \mathbb{E}[X_n] &= \sum_{i=1}^n\mathbb{E}[X_n\mid B_i]\Pr(B_i) = \frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_n\mid B_i] \end{align} }[/math].

而当事件[math]\displaystyle{ B_i }[/math]发生时，即当pivot恰为数组[math]\displaystyle{ A }[/math]中第[math]\displaystyle{ i }[/math]小的元素， 算法会将[math]\displaystyle{ A }[/math]中比pivot小的[math]\displaystyle{ (i-1) }[/math]个元素放入子数组[math]\displaystyle{ L }[/math]、将比pivot大的[math]\displaystyle{ (n-i) }[/math]个元素放入子数组[math]\displaystyle{ R }[/math]，这总共会花费[math]\displaystyle{ n-1 }[/math]次比较。 而且，由于[math]\displaystyle{ L }[/math]和[math]\displaystyle{ R }[/math]的内部元素之间分别保持了原相对顺序，因此不难验证[math]\displaystyle{ L }[/math]和[math]\displaystyle{ R }[/math]各自内部元素的相对顺序，分别同分布于[math]\displaystyle{ (i-1) }[/math]元均匀随机排列和[math]\displaystyle{ (n-i) }[/math]元均匀随机排列。 因此，在[math]\displaystyle{ B_i }[/math]发生的情况下，递归调用QSort[math]\displaystyle{ (L) }[/math]和QSort[math]\displaystyle{ (R) }[/math]各自所使用的总比较次数分别为[math]\displaystyle{ X_{i-1} }[/math]和[math]\displaystyle{ X_{n-i} }[/math]。 综上所述，有如下恒等关系：

[math]\displaystyle{ \mathbb{E}[X_n\mid B_i] = \mathbb{E}[n-1+X_{i-1}+X_{n-i}] }[/math].

因此，上述全期望因此可被计算如下：

[math]\displaystyle{ \begin{align} t(n) = \mathbb{E}[X_n] &= \frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_n\mid B_i]\\ &= \frac{1}{n}\sum_{i=1}^n\mathbb{E}[n-1+X_{i-1}+X_{n-i}]\\ &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}\mathbb{E}[X_{i}] &\text{(linearity of expectation)}\\ &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i). \end{align} }[/math]

我们因此建立了平均复杂度[math]\displaystyle{ t(n)=\mathbb{E}[X_n] }[/math]的如下递归式：

[math]\displaystyle{ \begin{align} t(n) &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i) && \text{if }n\gt 1;\\ t(n) &= 0 && \text{if }0\le n\le 1. \end{align} }[/math]

我们有若干种方法从这一递归式获得关于[math]\displaystyle{ t(n)=\mathbb{E}[X_n] }[/math]的真相：

• 一种是使用生成函数等工具来求解这样的递归方程，例如使用本学期组合数学课上的分析，最终可精确解出[math]\displaystyle{ t(n)=2(n+1)H(n)-4n }[/math]，此处[math]\displaystyle{ H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1) }[/math]为第[math]\displaystyle{ n }[/math]个调和数；
• 另一种是采用数学归纳法来对我们猜想的关于[math]\displaystyle{ t(n) }[/math]的界进行验证，例如从[math]\displaystyle{ t(n)\le c n \ln n }[/math]的归纳假设出发，令[math]\displaystyle{ c }[/math]尽量小，不难验证[math]\displaystyle{ t(n)\le 4 n \ln n }[/math]。

快速排序算法的平均复杂度分析 II（基于期望的线性）

假设输入数组[math]\displaystyle{ A }[/math]中的元素，在从小到大排序之后为[math]\displaystyle{ a_1\lt a_2\lt \cdots a_n }[/math]。而令输入[math]\displaystyle{ A }[/math]为该[math]\displaystyle{ n }[/math]个数字的随机排列。

令随机变量[math]\displaystyle{ X }[/math]表示在该随机输入[math]\displaystyle{ A }[/math]下，快速排序算法使用的总比较次数。我们希望分析得到期望[math]\displaystyle{ \mathbb{E}[X] }[/math]的上界。

对[math]\displaystyle{ 1\le i\lt j\le n }[/math]，令布尔值随机变量[math]\displaystyle{ I_{ij}=I(A_{ij})\in\{0,1\} }[/math]指示如下事件的发生：

• [math]\displaystyle{ A_{ij} }[/math]：元素[math]\displaystyle{ a_i }[/math]和[math]\displaystyle{ a_j }[/math]在算法运行过程中被比较了。

容易验证：在算法运行过程中，任何元素对[math]\displaystyle{ a_i }[/math]和[math]\displaystyle{ a_j }[/math]之间至多只会进行一次比较。 因此总比较次数[math]\displaystyle{ X }[/math]可被计算如下：

[math]\displaystyle{ X=\sum_{i\lt j}I_{ij} }[/math].

根据期望的线性（linearity of expectation）：

[math]\displaystyle{ \mathbb{E}[X]=\sum_{i\lt j}\mathbb{E}[I_{ij}]=\sum_{i\lt j}\Pr(A_{ij}) }[/math].

因此接下来，仅需要针对每一对具体的[math]\displaystyle{ 1\le i\lt j\le n }[/math]，计算概率：

[math]\displaystyle{ \Pr(A_{ij})=\Pr(a_i\text{和}a_j\text{在算法中进行了比较}) }[/math].

定下任意一对具体的[math]\displaystyle{ 1\le i\lt j\le n }[/math]。 在算法运行之初（顶层递归调用），元素[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]显然有[math]\displaystyle{ a_i\lt a_j }[/math]、且同属于当前递归调用的输入数组[math]\displaystyle{ A }[/math]。 此时根据pivot的选取，有如下三种可能的情况：

1. pivot刚好选中[math]\displaystyle{ a_i }[/math]或[math]\displaystyle{ a_j }[/math]之一，此时[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]之间必被比较（因为pivot会与当前数组内的所有元素进行比较），因此事件[math]\displaystyle{ A_{ij} }[/math]确定发生；
2. [math]\displaystyle{ a_i\lt }[/math]pivot[math]\displaystyle{ \lt a_j }[/math]，即pivot取值在[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]之间，此时[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]会被大小居于其中间的pivot元素分别分流到子数组[math]\displaystyle{ L }[/math]与[math]\displaystyle{ R }[/math]中，且在之后的递归调用中永不再见，因此不会被比较，事件[math]\displaystyle{ A_{ij} }[/math]确定不发生；
3. pivot选中了比[math]\displaystyle{ a_i }[/math]更小或者比[math]\displaystyle{ a_j }[/math]更大的元素，在此情况下[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]，连同它们之间的所有元素[math]\displaystyle{ \{a_k\mid i\lt k\lt j\} }[/math]，都会被分到同一个子数组[math]\displaystyle{ L }[/math]或者[math]\displaystyle{ R }[/math]中，而此时[math]\displaystyle{ A_{ij} }[/math]的发生与否尚未确定，需要递归至下一层（而且输入是[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]所同属的那个子数组）再确定。

不难看出，上述三种情况的分析，对于任意[math]\displaystyle{ A_{ij} }[/math]发生与否尚未确定的当前递归调用（即[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]同属于当前递归调用的输入数组），都仍然是成立的。 从而，上述情况分类可不断递归进行下去，直至事件[math]\displaystyle{ A_{ij} }[/math]的发生与否被完全确定下来。

因此，可以得出：[math]\displaystyle{ A_{ij} }[/math]发生，当且仅当在上述情况（1）或（2）之一发生的前提下有（1）发生。 除此之外，如下两个观察通过递归验证易得：

• 当[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]同属于当前递归调用的输入数组时，它们之间的所有元素[math]\displaystyle{ \{a_k\mid i\lt k\lt j\} }[/math]也属于该数组；
• 在任何递归调用中，pivot始终在当前输入数组中均匀分布。

综上可得：

[math]\displaystyle{ \Pr(A_{ij})=\Pr(\mathsf{pivot}\in\{a_i,a_j\}\mid\mathsf{pivot}\in\{a_i,a_{i+1},\ldots,a_{j}\})=\frac{2}{j-i+1} }[/math].

算法总比较次数的期望[math]\displaystyle{ \mathbb{E}[X] }[/math]可被计算如下：

[math]\displaystyle{ \begin{align} \mathbb{E}\left[X\right] &= \sum_{i\lt j}\Pr(A_{ij})\\ &\le \sum_{i=1}^n\sum_{j=i}^n\frac{2}{j-i+1}\\ &= \sum_{i=1}^n\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\mbox{Let }k=j-i+1)\\ &\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\ &= 2n\sum_{k=1}^{n}\frac{1}{k}\\ &= 2n H(n). \end{align} }[/math]

此处[math]\displaystyle{ H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1) }[/math]为第[math]\displaystyle{ n }[/math]个调和数。