斯坦福算法专项课程Course1 week3内容回顾

这周的内容主要是介绍了Quick Sort并分析其平均运行时间。

课程地址：https://www.coursera.org/specializations/algorithms

Course 1 Week 3

回顾排序问题

• Input: n个数字的未排序数组
• Output: 数组按递增顺序排列

这里假设元素都不相同。

这周来讨论Quick Sort，它是一种和Merge Sort不同的排序算法，在实际中更常用，下面详细回顾下：

Quick Sort

在介绍Quick Sort之前，先考虑一种叫Partition的方法：

Partition

选择一个pivot，对数组进行重新排列，使得pivot左边的元素都小于pivot，pivot右边的元素都大于pivot，这个过程叫Partition。

Partition的特点

• 1.可以在$O(n)$时间内完成，并且不需要额外的空间
• 2.减小了问题的规模

这里重点说下第一点。

我们先考虑空间的问题，我们使用交换元素的方式来处理，问了叙述方便，我们假设第一个元素为pivot（如果不是，和第一个元素交换即可），我们将数组分成三个部分：pivot，Already partitioned，unpartitioned，Already partitioned又细分为小于pivot以及大于pivot的部分，可以用下图表示：

接着，我们记$i,j$分别为Already partitioned中大于pivot的部分的第一个元素的位置和unpartitioned部分的第一个元素的位置，假设数组为$a$，长度为$n$。考虑$a[j]$，如果$a[j]<\text{pivot}$，那么说明$a[j]$应该属于小于pivot的部分，所以交换$a[i],a[j]$即可，交换之后$i=i+1,j=j+1$，如果$a[j]>\text{pivot}$，那么说明$a[j]$应该属于大于pivot的部分，这样就不用交换，直接$j=j+1$即可，当这个过程停止时，只要把pivot和大于pivot的部分的前一个元素交换，即pivot与$a[i-1]$交换即可。

这么说太抽象，我们看下图：

这个过程可以总结为如下伪代码：

从上述伪代码中可以看出运行时间为$O(n),n=r-l+1$，$n$为子串的长度，并且上述过程中只要交换两个元素，不需要开辟新的空间，这对数据很多的情形是很有利的。

Quick Sort算法

从Partition出发，可以给出Quick Sort算法：

Choosing a Good Pivot

到目前为止，我们还没分析算法的时间复杂度，这是因为不同的Pivot会影响算法的效率，来看两个例子：

Quiz 1

假设一个序列已经从小到大排序，现在使用Quick Sort，每次都选择第一个元素（最小的元素）作为Pivot，那么Quick Sort的时间复杂度为：

• 无法回答
• $\theta(n)$
• $\theta(n \log n)$
• $\theta(n^2)$

假设数组的长度为$n$，由Partition的过程我们知道，由于Pivot为最小元素，所以只存在大于Pivot的部分，这部分的长度为$n-1$，而一轮Partition需要的时间为$n$，从而时间复杂度满足下式：

$$\begin{aligned} T(n)&= T(n-1) +n\\ T(n)&= \sum_{i=1}^n i\\ &= \frac{n(n+1)}{2}\\ &=\theta(n^2) \end{aligned}$$

所以答案为$\theta(n^2)$

Quiz 2

还是对一组数使用快速排序，假设每次选择的Pivot都为中位数，那么时间复杂度为：

• 无法回答
• $\theta(n)$
• $\theta(n \log n)$
• $\theta(n^2)$

因为Pivot为中位数，所以小于Pivot以及大于Pivot的部分大小规模都为$\frac n 2$，可以由如下递推式

$$T(n) = 2T(\frac n 2 )+\theta (n)$$

由主定理，$T(n) =\theta(n\log n)$

从两个问题来看，Pivot的选择对于算法的性能有很大的影响，对于这种算法，我们来研究它的平均时间复杂度，我们来看下面的定理。

Average Running Time of QuickSort

对于每个长度为$n$的输入，QuickSort的平均时间复杂度为$O(n\log n)$

注意，这里的平均是针对pivot为随机的意思，因为要研究随机现象，所以必然要引入概率，我们来指出样本空间以及随机变量，总结如下：

样本空间$\Omega$：QuickSort中所有很可能的随机选择的结果（例如pivot序列）

随机变量：对于$\sigma \in \Omega$，$C(\sigma)$为QuickSort算法中比较的次数

之所以比较考虑比较的次数，是因为QuickSort的时间复杂度由比较次数决定，所以接下来的任务为证明

$$E[C] = O(n\log n)$$

记$z_i$为$A$中第$i$小的元素，对于$\sigma \in \Omega$，假设$i<j$，记$X_{ij}(\sigma)$在序列$\sigma$下$z_i,z_j$比较的次数。

回顾QuickSort算法，可以发现任意两个元素最多比较一次，从而$X_{ij}(\sigma)\in \{0,1\}$，并且由$X_{ij}(\sigma)\in \{0,1\}$的定义可知有如下关系：

$$\forall \sigma ,C(\sigma) =\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}X_{ij}(\sigma)$$

对这个式子取期望可得

$$E[C(\sigma)] =\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}E[X_{ij}(\sigma)]$$

注意$X_{ij}(\sigma)\in \{0,1\}$，所以

$$\begin{aligned} E[X_{ij}(\sigma)]& =P[X_{ij}(\sigma)=1]= P(z_i,z_j进行了比较)\\ E[C(\sigma)] &=\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}P(z_i,z_j进行了比较) \end{aligned}$$

所以现在关键的问题是计算$P(z_i,z_j进行了比较)$，给出如下声明：

Key Claim

$$对于i<j,P(z_i,z_j进行了比较) = \frac{2}{j-i+1}$$

证明：

考虑$z_i,z_{i+1},…,z_{j-1},z_j$，如果$z_i,z_j$都不被选为pivot，那么它们不会进行比较，反之，如果$z_i,z_j$有一个被选为pivot，那么会比较一次，所以

$$对于i<j,P(z_i,z_j进行了比较) = \frac{2}{j-i+1}$$

将上述结论带入式子，可得

$$E[C(\sigma)] =\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}P(z_i,z_j进行了比较) =\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1}$$

先计算内部的和式：

$$\sum_{j=i+1}^{n} \frac{2}{j-i+1} = 2 \left(\frac{1}{2}+...+\frac{1}{n-i+1} \right) \le 2\left(\frac{1}{2}+...+\frac{1}{n}\right)=2\sum_{k=2}^n \frac 1 k$$

我们来估计$2\sum_{k=1}^n \frac 1 k$，可以利用$y=\frac 1 x$的图像来估计，有下图：

由图像可得如下不等式

$$\sum_{k=2}^n \frac 1 k \le \int _1 ^n \frac 1 x dx = \ln n$$

从而

$$\begin{aligned} \sum_{j=i+1}^{n} \frac{2}{j-i+1} &= 2\sum_{k=2}^n \frac 1 k \le 2 \ln n \\ E[C(\sigma)]& =\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1} \le 2 \sum_{i=1}^{n-1} \ln n \le 2n\ln n\\ E[C(\sigma)] & = O(n\log n) \end{aligned}$$