斯坦福算法专项课程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之前,先考虑一种叫Partion的方法:

Partion

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

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

这里重点说下第一点。

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

接着,我们记$i,j$分别为Already partioned中大于pivot的部分的第一个元素的位置和unpartioned部分的第一个元素的位置,假设数组为$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算法

从Partion出发,可以给出Quick Sort算法:

Choosing a Good Pivot

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

Quiz 1

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

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

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

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

Quiz 2

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

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

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

由主定理,$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的时间复杂度由比较次数决定,所以接下来的任务为证明

记$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\}$的定义可知有如下关系:

对这个式子取期望可得

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

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

Key Claim

证明:

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

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

先计算内部的和式:

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

由图像可得如下不等式

从而