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

这周的内容主要是再介绍了几个Divide and Conquer的例子,最后给出了分析时间复杂度的Master Method。

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

Course 2 Week 2

The Closest Pair Problem

  • Input:$\mathbb R^2$中$n$个点$P=\{p_1,…,p_n\}$
  • Notation:$d(x_i,x_j)$为欧几里得距离
  • Output:$P$中两个距离最近的点$p,q$

这里我们假设每个点的横坐标,纵坐标均不相同。

这个问题的一维情形可以用排序解决,时间复杂度为$O(n\log n)$,二维情形如果暴力求解,那么时间复杂度为$\theta(n^2)$,现在的目标是把二维情形的时间复杂度降低到$O(n\log n)$。

我们先把这些点按$x$排序为$P_x$,按$y$排序为$P_y$,这一步需要$O(n\log n)$的时间,但这样做显然是不够的,后面还需要Divide+Conquer,伪代码如下:

备注:$Q_x$为$P_x$的前半部分,按$x$轴排序;$Q_y$为$P_x$的后半部分,按$y$轴排序。

这个算法的关键是第5步,如果这个步骤只需要花$O(n)$的时间,那么由上一周的讨论我们知道,这个算法总共需要的时间为$O(n\log n)$,所以现在问题就转换为ClosestSplitPair的问题,这里老师先给出算法:

补充一下,上图中的$S_y$的描述有误,应该为横坐标$x\in [\overline x - \delta , \overline x +\delta]$的点按照纵坐标$y$排序之后的点集。

这个算法最神奇的地方在于,第二重循环只要执行7次,所以保证了时间复杂度为$O(n)$,下面来解释下这个算法,有如下命题:

令$p\in Q, q\in R$为$d(p,q) < \delta$的split pair,那么

  • (A) $p,q \in S_y$
  • (B)$p,q$在$S_y$中最多距离$7$位

令$p=(x_1,y_1),q=(x_2,y_2)$

命题(A)的证明:

因为$p\in Q, q\in R$,所以$x_1\le \overline x,x_2 \ge \overline x$,而$|x_1-x_2| \le d(p,q) <\delta$,因此$x_1,x_2 \in [\overline x - \delta , \overline x+\delta]$

命题(B)的证明:

先画出以下关键图形:

证明命题(B)需要以下两个引理:

引理1:$S_y$中纵坐标范围介于$p,q$纵坐标之间的点都落在这8个方格之内。

引理2:1个方格内最多有1个点。

引理1的证明:

首先$|y_1-y_2| \le d(p,q) <\delta$,说明满足条件的点的纵坐标落在方格的纵坐标范围内,其次$S_y$中的点横坐标的范围为$ [\overline x - \delta , \overline x+\delta]$,结合以上两点,满足条件的点都落在这8个方格之内。

引理2的证明:

反证法,如果有两个点落在同1个方格内,或者这两个点都属于$Q$,或者都属于$R$,无论那种,这两个点的距离小于等与正方形的对角线的长度$\frac{\sqrt 2 \delta}{2}<\delta$,这与$\delta$的定义相矛盾,所以引理2成立。

结合这两个引理可知如果split pair中两点距离小于$\delta$,那么这两个点都属于$S_y$,并且$S_y$中的下标差不会超过7,从而算法是正确的。

Counting Inversions

  • Input: 含有数字1,2,…,n任意顺序的数组
  • 逆序数(inversions)的数量,即满足$ia[j]$的二元组$(i,j)$的数量

这个问题还是用Divide and Conquer,有如下算法

这个算法最重要的是解决CountSplitInv部分,即计算$i\le \frac n 2 \le j$,但是$a[i]>a[j]$的数量,和之前的算法一样,我们的目标是希望在$O(n)$的时间内解决这个问题,解决之后就可以使得该算法的运行时间为$O(n\log n)$。

但是上述算法可能无法很好地解决该问题,所以这里老师给出一个更强的算法,在计算数量的同时给数组排序,如下:

由B,C推出D的过程为merge,操作和归并排序里一样,以一个具体例子来观察merge操作和逆序数数量的关系

将这个过程总结一下,有如下命题:

split inversions的逆序数量为将第二段数组C中元素$y$复制到D时B中剩余元素的数量之和。

证明:

令$x$为第一段数组B中的元素

1.如果$x$在$y$之前被复制到D,那么$x<y$,说明$(x,y)$不是逆序对。

2.如果$y$在$x$之前被复制到D,那么$y<x$,说明$(x,y)$是逆序对并且$x$之后的数字和$y$都组成逆序对。

因为merge的时间为$O(n)$,所以这个算法的时间为$O(n\log n)$

Matrix Multiplication

如果将每个$n\times n$矩阵拆为$4$个$\frac n2\times \frac n2$,利用Divide and Conquer,有如下算法

这个算法将原问题拆成$8$个子问题,时间复杂度为$\theta(n^3)$,而直接计算的方法也为$\theta(n^3)$,说明这个算法没有提升速度,这时老师介绍了一个神奇的算法:

这个算法的神奇之处为将原问题拆成$7$个子问题,利用主定理,可以计算出时间复杂度小于$\theta(n^3)$。

接下来回顾主定理。

Master Method

我们之前讨论的很多算法的时间复杂度都可以写为如下形式

例如Merge Sort

Karatsuba Multiplication

Master Method描述的就是$T(n) \le aT(\frac n b) + O(n^d)$可以推出怎样的时间复杂度,我们对原条件变形一下

那么同Merge Sort的算法时间推导过程,可以画出如下树状图

那么第$j$层的时间复杂度小于等于

一共的时间复杂度小于等于

现在讨论这个式子,可以看出,这个式子和$a,b^d$的大小关系有关,分三种情况讨论:

(1) $a = b^d$

那么时间复杂度小于等于

从而时间复杂度为

讨论其余两种情况之前,先考虑等比级数

如果$r<1$,那么

如果$r>1$,那么

利用这两个结论继续讨论:

(2) $a>b^d$

此时$\frac{a}{b^d} >1$,由等比级数的性质,我们知道

所以时间复杂度为

(3) $a<b^d$

此时$\frac{a}{b^d} <1$,由等比级数的性质,我们知道

所以时间复杂度为

综合以上三种情形,可以得到Master Method:

如果

那么