这周的内容主要是介绍了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

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

Analysis

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

接下来我们来分析$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$条件下某个事件第一次发生的概率,这实际上是几何分布,满足如下性质:

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

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

这说明算法的平均时间复杂度为$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(?)$是步骤6,7产生的,现在的问题是计算$T(?)$的规模,我们有如下引理:

The Key Lemma

证明这个引理之前,先给出如下记号:

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

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

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

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

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

换句话说,$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)$,所以我们的递推式为:

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

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

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

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

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

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

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

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

证明:

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

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

由斯特林公式

可以推出

从而

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

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$,这种表示方法还可以推广到边有权重以及无向图中,总结如下:

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

Adjacency Lists

邻接表有如下元素:

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

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

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$里的边被合并的事件,所以我们我们要计算的概率为:

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

很显然地,我们有

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

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

所以

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

同理可得

从而

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

接着利用

所以

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

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

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

Counting Mininum Cuts

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

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

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

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

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

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

所以结论成立。