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

这周的内容主要是介绍了Linear Time Selection以及图的基本知识。

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

Course 1 Week 4

Linear Time Selection

考虑如下问题

• Input: 有$n$个数字的数组$A$以及一个数字$i$（这里假设数字都不同）
• Output: 输出第$i$小的数字

如果我们先使用排序，再处理这个问题，那么需要的时间为$O(n\log n)$，现在的问题是能否找到更好的算法，我们先介绍Randomized Selection

Randomized Selection

回顾快速排序，在Partion之后，pivot左边的元素都小于pivot，pivot右边的元素都大于pivot，所以可以判断出pivot从小到大的次序$j$（等于小于pivot的元素个数加$1$）：

• 如果$i=j$，那么直接输出pivot。

• 如果$i<j$，那么在小于pivot的$j-1$个元素中找第$i$小的元素。

• 如果$i>j$，那么在大于pivot的$n-j$个元素中找第$i-j$个元素。

这样上述过程可以产生一个递归算法，描述如下：

上述算法之所以叫Randomized Selection，是因为这个算法的时间复杂度和pivot的选择有关，我们来看一个Quiz

Quiz

如果每次pivot都选择最糟糕的情形，Randomized Selection的时间复杂度为多少？

• $\theta(n)$
• $\theta(n \log n)$
• $\theta(n^2)$
• $\theta(2^n)$

假设$i=n$，每次都选择最小的的元素，那么一共要$n$次才能找到该元素，每次需要的时间为$\theta(n)$，所以一共的时间为$\theta(n^2)$

从这个例子中可以看出，同Quick Sort一样，我们应该给出尽可能平衡的划分，最好的pivot是中位数的位置，但这个是几乎不可能的，但是我们有如下定理：

Rselect Theorem

$$对每个长度为n的数组A，\text{Randomized Selection}的平均时间复杂度为O(n)$$

同Quick Sort一样，这里的平均时间复杂度是将pivot视为随机变量后得到的结果，接下来我们来证明这个定理。

Analysis

首先要注意上述算法的步骤2——Partion的时间正比于数组的长度$n$，不妨设比例系数为$c$，所以长度为$n$的数组Partion的时间小于等于$cn$。接来下来我们的目标是限制算法中步骤4，5的规模，考虑如下算法，在阶段$j$，我们不停地选择pivot，直到子问题的规模小于等于$(\frac 3 4 )^{j} n$再停止，记这个选择的次数为$X_j$，所以算法的时间复杂度$T(n)$有如下关系：

$$T(n) \le \sum_{j} X_j c \left(\frac 3 4 \right)^j n = cn \sum_{j} X_j \left(\frac 3 4 \right)^j$$

接下来我们来分析$X_j$，来看下第$j$轮子问题的规模小于等于$(\frac 3 4 )^{j} n$事件何时发生。考虑第$1$轮，我们要子问题的规模小于等于$(\frac 3 4 ) n$，如果我们取排名位于$\frac 1 4 n$到$\frac 3 4 n$的pivot，那么上述事件就会发生，由于是均匀选取，所以事件发生的概率为$\frac{\frac 3 4 n - \frac 1 4 n }{n}= \frac 1 2$，同理考虑第$j$轮也也可以得到相同的结论，从而上述问题转换为在$p=\frac 1 2$条件下某个事件第一次发生的概率，这实际上是几何分布，满足如下性质：

$$\begin{aligned} P(X_j = k) &= (1-p)^{k-1} p \\ E[X_j] &= \frac 1 p \end{aligned}$$

此处$p= \frac 1 2 $，所以$E[X_j]=2$。

利用上述结果估计$E[T(n)]$

$$E[T(n)] \le cn \sum_{j} E[X_j] \left(\frac 3 4 \right)^j =2cn \sum_{j} \left(\frac 3 4 \right)^j \le 2cn \frac{1}{1 -\frac 3 4} = 8cn$$

这说明算法的平均时间复杂度为$O(n)$。

接下来考虑更强的算法——Deterministic Selection，这个算法的时间复杂度为$O(n)$。

Deterministic Selection

我们的关键问题是选择pivot，可以给出如下总结。

• 回顾：“best” pivot = the median!

• 目标：找到相当好的pivot

• 关键想法：use “median of medians”!

从“median of medians”这个想法中，老师给出如下选择pivot的算法：

这个算法的思路就是“median of medians”：先选择$\frac n 5$个数，这$\frac n 5$都是每组的中位数，再对这个$\frac n 5$个数找他们的中位数。

利用选择pivot的算法，可以给出Deterministic Selection的算法：

接下来的任务是分析算法的时间复杂度，分析这个算法之前，我们先来看一个Quiz

Quiz

上述算法的步骤1需要的时间复杂度为多少？

• $\theta(1)$
• $\theta(\log n)$
• $\theta(n)$
• $\theta(n \log n)$

步骤1将数组拆成$\frac n 5$个大小为$5$的数组，然后对每个数组排序，由于对常数大小的数组排序的时间为$\theta(1)$，所以步骤1需要的时间复杂度为$\theta(n)$

有了这个结论，我们进入算法的分析。

Analysis I

设Determinis Selection的最大算法时间复杂度为$T(n)$，我们对每步都进行分析，可以得到下图：

上述图可以总结为如下式子

$$T(n) \le cn + T(\frac n 5) +T(?)$$

其中$T(?)$是步骤6，7产生的，现在的问题是计算$T(?)$的规模，我们有如下引理：

The Key Lemma

$$步骤6,7产生的递归一定在规模\le \frac 7 {10}n的数组上进行（粗略的）。$$

证明这个引理之前，先给出如下记号：

• $k =\frac n 5=$组数

• 令$x_i=k$个“middle elements”中第$i$小的元素，所以pivot$= x_{\frac k 2}$

可以用如下图像证明该引理：

同上图中可以看出，大于$x_{\frac k 2}$的元素数量至少为

$$3\times (k - \frac k 2 +1) -1 = \frac 3 2 k +2 = \frac 3 2 \frac n 5 +2=\frac 3 {10}n +2 > \frac 3 {10}n$$

小于$x_{\frac k 2}$的元素数量至少为

$$3\times (k - \frac k 2 +1) -1 = \frac 3 2 k +2 = \frac 3 2 \frac n 5 +2=\frac 3 {10}n +2 > \frac 3 {10}n$$

换句话说，$x_{\frac k 2}$一直位于$\frac 3 {10}n$到$\frac 7{10}n$的位置，从而子问题的规模小于等于$\frac 7{10}n$，引理得证。

结束这部分之前，再来看一个具体例子：

Analysis II

之前的引理即为$T(?)\le T(\frac 7{10}n)$，所以我们的递推式为：

$$T(n) \le cn + T(\frac n 5) +T(\frac 7{10}n)$$

这个式子无法使用主定理，但是可以使用数学归纳法来证明，取$a= 10c$，接下来我们来证明$T(n)\le a n$。

$n=1$时显然成立，假设$n< k$时，$T(n) \le a n$，那么$n=k$时

$$\begin{aligned} T(k) & \le ck + T(\frac 1 5 k ) +T(\frac 7{10}k)\\ &\le ck + a\frac 1 5 k + a \frac 7{10}k \\ &= ck + 2ck+7ck \\ &=10ck\\ &=ak \end{aligned}$$

所以$n=k$时结论也成立，从而$T(n) \le an$，定理得证。

An $\Omega(n\log n)$ Sorting Lower Bound

这一部分讨论排序算法的时间下界，我们有如下定理：

$$每个\text{“comparison based”}排序算法的时间下界为 \Omega(n\log n)$$

$\text{“comparison based”}$的含义是通过比较元素大小来进行排序。

这里给出一些$\text{“comparison based”}$算法的例子：

$$\text{Merge Sort,Quick Sort,Heap Sort}$$

非$\text{“comparison based”}$算法的例子：

$$\text{Bucket Sort, Counting Sort,Radix Sort}$$

证明：

长度为$n$的数组一共有$n!$中排列方式，$\text{“comparison based”}$算法可以用树状图表示，如下：

从树状图可以看出，$k$次比较一共产生了$2^k$个结果，所以如果我们要包括全部的排列方式，必然有

$$2^k \ge n!$$

由斯特林公式

$$n! \approx (\frac{n}{e})^n \sqrt{2\pi n}$$

可以推出

$$k \ge \log_2 n! \ge \log_2 \left(\frac{n}{e}\right)^n = n \log_2 \left(\frac{n}{e}\right)$$

从而

$$k= \Omega(n\log n)$$

这周后一半的内容是介绍图。

Graph

Representing Graphs

图有两个元素，节点$V$和边$E$，边根据是否有向又分为有向图以及无向图。

来看一个图的例子：

根据定义，来看一个Quiz

Quiz 1

有$n$个点的无向图，没有平行边，并且是连接的（每个节点都有边相连），那么最少和最多的边的数量分别为多少？

• $n-1, \frac{n(n-1)}{2}$
• $n-1, n^2$
• $n-1, 2^n$
• $n-1, n^n$

因为每个节点都有边相连，所以至少要$n-1$条边，由于没有平行边，所以最多有$C_n^2 = \frac{n(n-1)}{2}$条边。

Sparse vs Dense Graphs

令$n=$图中节点的个数，$m=$图中边的个数，$m$一般满足$\Omega(n)$以及$O(n^2)$。

如果$m =O(n)$，那么称为“稀疏”图；如果$m =\theta(n^2)$，那么称为“密集”图。

接着介绍两种图的表示方法。

The Adjacency Matrix

邻接矩阵法使用一个$n\times n$的矩阵$A$表示图，将节点分别给出$1$到$n$的编号，如果节点$i,j$直接有边相连，那么$A_{ij} =1$，否则$A_{ij} =0$，这种表示方法还可以推广到边有权重以及无向图中，总结如下：

$$\begin{aligned} A_{ij} & = i,j之间边的个数\\ A_{ij} & = i,j之间的权重\\ A_{ij} & =\begin{cases} 1, & \text{如果存在i到j的边}\\ -1, & \text{如果存在j到i的边} \end{cases} \end{aligned}$$

可以看到，邻接矩阵表示图需要的空间为$\theta(n^2)$。

Adjacency Lists

邻接表有如下元素：

分别为节点，边，每条边指向的节点，每个节点出发的边，占用的空间复杂度为

$$\theta(\max\lbrace m,n\rbrace ) = \theta(m+n)$$

这门课程中一般都用邻接表来表示。

The Minimum Cut Problem

下面来讨论Minimum Cut问题。

• Input：一个无向图$G = (V,E)$(允许平行边)
• Output：找到一个cut，使得该cut穿过的边最少(Minimum Cut)

来看一张图：

这里老师直接给出如下算法：

Random Contraction Algorithm

注意这个算法是随机算法，所以有可能会失败，下面给出两个例子，分别对应成功与失败。

成功：

失败：

所以现在的关键问题是，这个算法成功的概率是多少？

The Analysis

在分析之前，先给出如下记号：

图$G=(V,E)$有$n$个顶点，$m$条边，固定一个minimum cut$ (A, B)$，$F$为穿过$(A,B)$的边的集合，$k$为$F$中边的个数，如下图所示：

我们来计算输出为 $ ( A, B)$的概率。

分析算法的过程，我们可知，输出为 $ (A, B)$当且仅当$F$中的边没有被合并，令$S_i$为第$i$轮$F$里的边被合并的事件，所以我们我们要计算的概率为：

$$\Pr[\overline S_1 \overline S_2... \overline S_{n-2}]$$

其中$\overline S_i$表示$S_i$不发生，下标到$n-2$是因为剩下$2$个节点就停止算法，每一轮减少一个节点，所以需要$n-2$轮。

很显然地，我们有

$$\Pr[S_1] = \frac{\sharp \text{crossing edge}的数量}{\sharp 边的总数} = \frac{k}{m}$$

在继续讨论之前，定义度(degree)为每个节点连接的边的数量，显然我们有如下等式：

$$\sum_v \text{degree}(v) = 2m$$

由minimum cut的定义可知，每个边的度都大于等于$k$，而一共有$n$个点，所以可得如下不等式：

$$\begin{aligned} 2m &\ge k n\\ \frac{k}{m} &\le \frac 2 n \end{aligned}$$

所以

$$\begin{aligned} \Pr[S_1] &= \frac{k}{m}\le \frac 2 n \\ \Pr[\overline S_1] &\ge 1- \frac 2 n \end{aligned}$$

现在第一步已经完成，我们来考虑第二步。第二步相当于在$n-1$个节点中找边数为$k$的minimum cut，设此时的边的数量为$m’$，上述讨论依旧成立，从而

$$\begin{aligned} 2m' &\ge k(n-1) \\ \frac k {m'}& \le \frac{2}{n-1}\\ \Pr[\overline S_2| \overline S_1] &= 1 -\frac{k}{m'} \ge 1-\frac{2}{n-1} \end{aligned}$$

同理可得

$$\Pr[\overline S_i| \overline S_1...\overline S_{i-1}] \ge 1 - \frac{2}{n+1 - i}$$

从而

$$\begin{aligned} \Pr[\overline S_1 \overline S_2... \overline S_{n-2}] &= \Pr[\overline S_1] \Pr[\overline S_2 |\overline S_1 ]... \Pr[\overline S_{n-2}| \overline S_1...\overline S_{n-3}] \\ & \ge (1- \frac 2 n ) (1- \frac 2 {n-1} ) ...(1- \frac 2 {3} ) \\ &= \frac{(n-2)!\times 2}{n! } \\ &=\frac{2}{n(n-1)}\\ &\ge \frac 1 {n^2} \end{aligned}$$

可以看到，成功的概率很低，但是这只是一次实验的概率，而我们可以进行很多次实验，假设我们进行$N$次实验，那么：

$$\Pr [N次实验均失败] = (1- \Pr[\overline S_1 \overline S_2... \overline S_{n-2}]) ^N \le (1-\frac 1 {n^2})^N$$

接着利用

$$1+x \le e^x$$

所以

$$\Pr [N次实验均失败] \le (1-\frac 1 {n^2})^N \le e^{-\frac{N} {n^2} }$$

如果取$N= n^2$，那么

$$\Pr [N次实验均失败] \le (1-\frac 1 {n^2})^N \le e^{-\frac{N} {n^2} } = e^{-1}$$

如果取$N = n^2 \ln n$，那么

$$\Pr [N次实验均失败] \le (1-\frac 1 {n^2})^N \le e^{-\frac{N} {n^2} } = e^{-\ln n} =\frac 1 n$$

可以看到，如果实验次数足够多，全部失败的概率就会很小。

Counting Mininum Cuts

现在考虑另一个问题，计算Mininum Cuts的数量，之所以讨论这个问题，因为图可能有多个Mininum Cuts，例如节点个数为$n$的树有$n-1$个Mininum Cuts，这里老师直接给出结论：

$$节点数为n图的\text{Mininum Cuts}的数量最多为\frac {n(n-1)}{2}$$

分两步证明，分别证明大于等于以及小于等于。

先证明大于等于的关系，考虑下图的圆环。

显然Mininum Cuts有$2$条边，所以圆环情形至少有$C_n^2= \frac {n(n-1)}{2}$种Mininum Cuts，从而

$$节点数为n图的\text{Mininum Cuts}的数量的最大值\ge \frac {n(n-1)}{2}$$

再证明小于等于的关系，令$(A_1,B_1),…,(A_t,B_t)$为全部Mininum Cuts，由上一部分的讨论可知

$$\Pr[\text{Output} = (A_i,B_i)] \ge \frac{2}{n(n-1)}$$

因为$(A_i,B_i)$是互斥事件（每一次只输出一个结果），所以这些事件加起来的概率小于等于$1$，从而

$$\begin{aligned} \frac{2t}{n(n-1)}&\le 1 \\ t &\le \frac{n(n-1)}{2} \end{aligned}$$

所以结论成立。