【高级数据结构与算法分析】课程笔记

成绩：

96/100

，绩点

5.0

希望能以尽量简洁的方式对 ads 的各个知识点做一个梳理

AVL Tree

定义：对一棵二叉搜索树，如果每个节点都满足：左右子树高度相差不超过

1

，则这棵树就是一个 AVL 树

那么显然高度为

h

的 AVL 树的节点数至少是斐波那契数，故树高还是

O(\log size)

的

插入

从根节点往下递归，根据当前节点元素和插入元素的大小关系决定向左子树还是向右子树递归

最后递归至空节点，此时完成插入操作

删除

如果待删除节点为叶子节点，则直接删除
如果待删除节点只有左子树或只有右子树，则删除该节点，把它唯一一棵子树接上去
否则，选出左子树中最大的那个或者右子树中最小的那个与其交换，并删除

性质维护

由于插入和删除至多只会造成高度差

=2

的问题，因此关注违反性质的两层节点：

如果高的那个子树（是唯一的）向上两层朝向一致，则旋转父节点一次
否则，旋转子树根节点两次
同时，并不需要显式地区分左旋和右旋

一共有四种情况，这里只列出来两种，另外两种旋转模式是对称的

Splay Tree

Splay 与 AVL 非常类似，但是它不需要维护子树高度，而是只通过旋转来保证

O(\log n)

的单次均摊复杂度

这个复杂度的含义为：从空树开始的任意

m

次连续的操作所需的时间为

O(m\log n)

，其中

n

为树的大小

注意这里只说了

m

次操作的总时间，因此单次操作的复杂度开销可能很高（例如访问一个深度很大的节点），因此无论何时，在访问到一个节点之后，都需要将其旋转至根

旋转操作：Splay

设当前节点为

u

，父节点为

x

，祖父节点为

y

（如果存在的话）

$x$ 为根，此时直接旋转 $u$ 即可
否则：
- $u,x$ 朝向相同（同为左儿子/右儿子），则先旋转 $x$ ，再旋转 $u$
- $u,x$ 朝向不同，则旋转两次 $x$

插入操作

按正常 BST 插入流程操作，插入完成之后将这个节点 splay 至根

删除操作

先找到待删除节点，将其 splay 至根，然后：

根节点为叶子节点，则直接删除，树删空
根节点没有左儿子或右儿子，则直接删除，并将子节点设为新的根
否则，取出左子树中最大值或右子树中最小值，将其 splay 至根，此时原来的根是只有一个儿子的，那么删掉原来的根，将这个儿子接到新树根下即可

Inverted File Index

似乎只考这个东西：

	Relevant	Irrelevant
Retrieved	$R_R$	$I_R$
Not Retrieved	$R_N$	$I_N$

然后得到：

Precision： $P=R_R/(R_R+I_R)$
Recall： $R=R_R/(R_R+R_N)$

Leftist Heaps

除了插入/删除堆顶，我们还希望能够做到快速合并两个堆，从而引出了左偏堆这种结构

定义：记节点

x

的空路径 Null path length（Npl）为到其子树内最近一个少于两个儿子的节点的距离，特别地，定义 Npl(NULL)=-1

性质：显然，

\operatorname{Npl}(x)=\min(\operatorname{Npl}(ls(x)),\operatorname{Npl}(rs(x)))+1

那么左偏堆满足：

堆序：即若为小根堆，则父节点元素不大于子节点元素
对每个节点 $x$ ，有 $\operatorname{Npl}(ls(x))\ge \operatorname{Npl}(rs(x))$

性质：

若某个左偏堆的最右链包含 $r$ 个节点，那么这个左偏堆的大小至少是 $2^r-1$
于是，如果某个左偏堆包含 $n$ 个节点，那么最右链的长度不超过 $\log(n+1)$

因此，如果可以将所有操作和最右链的长度挂钩，那么就可能做到较好的复杂度

合并操作

（下文以小根堆为例，另外，插入操作相当于合并一个单点，故略去不谈）

递归版本

假设目前需要合并以

H_1,H_2

为根的两个左偏堆：

若 $H_1,H_2$ 有至少一个为空，那么直接接上另一个堆即可
否则，假设 $H_1<H_2$ $H_{1} < H_{2}$ ，然后
- 合并 $H_1$ 的右子树与 $H_2$ （即：merge(rs(H1),H2)）
- 在合并完之后，调整 $H_1$ 的左右儿子以满足 $\operatorname{Npl}$ 的大小关系
- 更新 $H_1$ 的 $\operatorname{Npl}$ 值，合并之后堆的根节点为 $H_1$

这样合并的复杂度为两个堆的最右链长度之和，即

O(\log size)

（这个复杂度是严格的）

迭代版本

将两个左偏堆的最右链拿出来归并形成一条新的最右链，同时保持最右链上每个节点的左儿子不变

归并完之后，从下往上调整左右儿子是否交换，以及更新

\operatorname{Npl}

即可

在手动模拟的时候会方便很多

删除操作

弹出堆顶，相当于合并根节点的左右子树，显然左右子树依然是左偏堆

Skew Heaps

斜堆和左偏堆的关系非常类似于 Splay 和 AVL 之间的关系，不再关心 Npl

合并操作

依旧以小根堆为例

递归版本

假设目前需要合并以

H_1,H_2

为根的两个斜堆：

若 $H_1,H_2$ 有至少一个为空，那么直接接上另一个堆即可
否则，假设 $H_1<H_2$ $H_{1} < H_{2}$ ，然后
- 交换 $H_1$ 的左右儿子
- 合并 $H_1$ 的左子树与 $H_2$ （即：merge(ls(H1),H2)）
- 合并之后堆的根节点为 $H_1$

迭代版本

将两个斜堆的最右链拿出来，将这些点中每个点的左儿子交换到右侧，然后将这些点归并形成一条新的最左链

在手动模拟的时候会方便一点

复杂度分析

与 Splay 类似，斜堆的复杂度分析也需要在均摊意义下进行，同时由于插入和删除都是合并的特殊情形，因此只关注合并

定义：称一个节点

x

是重节点（Heavy Node）当且仅当 $x$ 的右子树大小大于等于 $x$ 的左子树大小，若不满足，则称 $x$ 是轻节点（Light Node）

那么定义一个局面

D

的势能函数

\Phi(D)

为当前局面中重节点的个数

然后分析合并操作的均摊代价：

由于在合并前后，只有两个斜堆的最右链中节点的轻重性质会发生改变，因此设 $h_{1/2},l_{1/2}$ 分别表示两个斜堆最右链上重节点和轻节点的个数

实际代价 $T_w=h_1+l_1+h_2+l_2$ 为两个斜堆的最右链长度之和
势能变化量（非最右链的节点轻重性质不变，设这部分节点中重节点个数为 $H$ $H$ ）
- $\Phi_1=h_1+h_2+H$
- $\Phi_2\le l_1+l_2+H$ （解释一下，原最右链上的重节点在合并时先交换左右儿子，然后在左子树内合并，因此左子树会变得更大，从而原重节点一定变成轻节点；同时轻节点可能变成重节点也可能不变）
因此均摊代价 $T_a=T_w+\Phi_2-\Phi_1\le 2(l_1+l_2)=O(\log n)$ （最右链上轻节点个数 $\le \log n$ ，因为从下往上每经过一个轻节点子树大小至少翻倍

Backtracking

原理：穷举所有的可能性，并剪枝（pruning）一部分无需搜索的内容

如果解有无穷多种可能性呢？
如果解很多（指数级/阶乘级）呢？

Eight Queens

著名的八皇后问题，在

8\times 8

的棋盘上放置

8

个皇后，满足任意两个皇后都无法彼此攻击

暴搜做法非常简单，按行新加一个皇后之后，判一下与之前的皇后在斜向及竖向是否会攻击到即可

注意：

n

皇后问题的解空间大小为

n!

（即需要检查

n!

个可能的解）

搜索树：将暴搜的过程用树形结构表示出来，从而剪枝就代表了舍弃一个子树不往里面递归

Turnpike Reconstruction Problem

问题：

数轴上有

n

个未知的点

x_1,x_2,\cdots,x_n

，已知

0=x_1<x_2<\cdots<x_n

，和

n

个点两两距离（共

n(n-1)/2

个距离）

构造出任意一组满足条件的点集

例如：

给出距离集合

D=\{1,2,2,2,3,3,3,4,5,5,5,6,7,8,10\}

，那么通过

|D|=15

可知

n=6

$x_6=10$ ，因为最大距离为 $x_n-x_1$
考虑次大距离，可知 $x_{n-1}-x_1=8$ 或 $x_n-x_2=8$ ，即存在两种不同的情况，这两种情况都需要进行搜索，在确定 $x$ 值后，删除相应的距离并递归下去
再不断考虑当前最大的距离即可，每个最大距离都有两种可能性，即是到开头还是到末尾

（可以给出这个做法的时间复杂度的上界为

O(2^nn^2)

，但实际运行情况可能会比较好）

Tic-tac-toe（井字棋）

广为人知的一个游戏

对于这类问题，实际上是有两个玩家在进行博弈，因此会有类似

\min-\max

搜索的效果

Minimax Strategy

定义

W_A,W_B

分别为当前局面下玩家

A,B

能获得胜利的方案数，例如：

CPP

* A *
* B *
* * *

此时就有

W_A=4,W_B=6

CPP

A A A  A A *  * A A  * A *  |  B A *  * A B  * A *  B A *  * A B  * A *
* B *  A B *  * B A  * B *  |  * B *  * B *  B B B  B B *  * B B  * B *
* * *  A * *  * * A  A A A  |  * * B  B * *  * * *  B * *  * * B  B B B

那么定义局面的的

W

值为

W_A-W_B

，那么显然先手会最大化

W

，后手会最小化

W

，体现在搜索树上，就是一层取子节点最大值，一层取子节点最小值，两种状态交替进行

$\alpha-\beta$ pruning

上图中，已经搜索完

44

对应的子树和

40

对应的子树，那么可以知道：

根节点值 $\ge 44$ ，且取子节点 $\max$
右儿子值 $\le 40$ ，且取子节点 $\min$

那么就可以判定，黑色节点无论取值多少，都无法影响到根节点的值了，那么此时就可以剪掉这部分搜索

同理还有这种情况，黑色节点部分也不需要再进行搜索了

NP-Completeness

这一章将讨论一些非常困难的问题，先举几个例子：

欧拉回路问题（容易）、哈密尔顿回路问题（困难）
最短简单路径问题（容易）、最长简单路径问题（困难）

说这些问题困难，是因为这些问题目前还没有多项式时间的确定性算法

什么是算法？

定义：算法是解决某个问题的一系列步骤，接受（也可以没有）输入，产生输出（必须有），同时每一步必须是良定义的，同时整个算法过程可以在有限的时间内结束

不可判定问题（Undecidable Problems）

哥德尔证明了任何公理系统都是不完备的，换言之，不存在一套理论能证明所有命题

最著名的不可判定问题是图灵停机问题（Halting Problem）：

是否存在一个算法能够识别所有的死循环？

另一个不可判定问题是 Post Correspondence Problem：

给出 $n$ 种骨牌，均有无限个，每个骨牌分成两半，每一半有一个字符串，问是否存在一种有限长的安排骨牌的方式，满足上下半所有字符串拼接起来相同
若字符集大小至少为 $2$ ，则这个问题是不可判定的

两种图灵机（Turning Machine）

确定性图灵机（Deterministic Turing Machine）

每一步执行一条指令，并跳转至下一条指令

非确定性图灵机（Nondeterministic Turing Machine）

每一步执行一条指令，并跳转至集合中的任意一条指令中，若其中某一条指令能得到解，那么一定会选择这条指令

NP: Nondeterministic Polynomial-time

称一个问题是 NP 的，当且仅当这个问题可以在多项式时间内被非确定性图灵机解决（这里的多项式时间，指的是与输入量形成多项式关系）

换言之，如果可以再多项式时间内验证任意一个解的正确性，那么这个问题就是 NP 的

例如：哈密尔顿回路问题是 NP 的，因为很容易验证一个解是不是一个哈密尔顿圈

类似地，P: Deterministic Polynomial-time

两类问题的关系

显然

P\sube NP

，但是是否有

P\sub NP

呢？目前仍然不知道

NPC: NP-Complete

这是所有 NP 问题中最难的一类，其中的最难，指的是如果解决了任意一个 NPC 问题，那么就能解决所有的 NP 问题（所有 NP 问题都能多项式时间规约到 NPC 问题）

换言之，所有的 NP 问题都是 NPC 问题的弱化版，得到了 NPC 问题的一个解，就能多项式时间得到到 NP 问题的一个解，同时所有 NPC 问题都是一样难的

第一个 NPC 问题

历史上第一个被证明 NPC 的问题是电路可满足性问题（Satisfiability Problem），即给出一个包含若干布尔变量的布尔表达式，问是否存在一种设置变量的方式，使得表达式的结果为真

（解决了这个问题，就能解决所有的 NP 问题）

一个例子

假设我们已经知道哈密尔顿回路问题是 NPC 的，那么如何导出 TSP 问题（给出一张带权完全图和参数

K

，问是否存在一个哈密尔顿回路边权之和

\le K

）也是 NPC 的

NP 性的证明：这个是比较显然的，给出一个解，显然容易验证边权和是否 $\le K$
规约：TSP 问题不弱于哈密尔顿回路问题，因为只需要把不出现的边的边权设置为 $\infty$ （一个较大的数就行），然后判定是否存在一个哈密尔顿回路边权之和 $\le n$ 即可，这样只要能做 TSP 问题，就能做哈密尔顿回路问题

NPH: NP-Hard

这类问题至少和 NPC 问题一样难，但是 NP-Hard 问题可能是无法在多项式时间内判定解的正确性的（因此可能会更难）

结论：

NPC=NP\cap NPH

一个例子

TSP 问题的优化版本（即求最小权哈密尔顿回路）就是 NPH 的，因为无法在多项式时间内验证这个解是 “最优” 的

Approximation Algorithms

一般来说，解决问题需要考虑三个方面：

是否最优？（optimality)
效率是否高？（efficiency）
是否普适？（all instances）

近似算法用于解决一些非常困难的问题（例如 NPC 问题），这种问题的处理办法通常有：

如果问题规模比较小，那么指数级（或者更高）复杂度的做法是可以接受的
可能存在一些做法能够高效解决问题的某些特殊情况
在多项式时间内得到问题的一个足够好的解（即近似算法 approximation algorithm）
- 注意，近似算法（approximation algorithm）和启发式算法（heuristic algorithm）是不一样的，近似算法通常可以证明近似比（解有多好），但启发式算法只是“人类智慧”

近似比

称一个算法对规模为

n

的数据有

\rho(n)

的近似比（approximation ratio，换言之，该算法是

\rho(n)

近似算法），当且仅当对任意数据：

设最优解为 $C^*$ ，算法给出的解为 $C$ ，那么有 $\max\left(\dfrac{C^*}{C},\dfrac{C}{C^*}\right)\le \rho(n)$ （这里有两项取 $\max$ 是因为一些问题是最大化，一些问题是最小化）

近似方案

一个近似方案（approximation scheme）同时以一组数据和一个参数

\varepsilon

为输入，满足当前算法是

(1+\varepsilon)

近似的

Polynomial-time approximation scheme（PTAS）

如果一个近似方案对任意固定的正数 $\varepsilon$ 都能在多项式时间内运行，则称其是一个 PTAS（多项式时间近似方案）

（这里，固定的正数表示我们不把

\varepsilon

当做变量，换言之，出现类似

O(n^{1/\varepsilon})

的复杂度是接受的）

另外，还有全多项式时间近似方案（Fully polynomial-time approximation scheme, F-PTAS），如果算法的运行时间关于

n

和

1/\varepsilon

都是多项式（例如

O((1/\varepsilon)^2n^3)

之类的）

Bin Packing Problem

问题：

给出

n

个物品，每个物品用其大小

s_i

描述，先有无穷多个大小为

1

的背包，问至少需要多少个背包可以装下所有物品

（这个问题是 NP-Hard 的，因为无法验证是否能用

K

个背包装下所有物品；但是它的判定版本是 NPC 的，因为给出一组分配方式之后，可以很容易得到背包个数是否

\le K

）

接下来介绍两种不同的近似方法：

Next Fit

从前往后一个一个装，如果放不下了就新开一个背包

这个做法的近似比为

2

，进一步地，如果最优解为

M

，则这个做法得到的结果

\le 2M-1

，同时这个上界是紧的（可以被构造到的）而它的证明也是容易的：

考虑反证，即最优解为

M

，且这个做法得到的结果为

2M

，那么设

W(i)

表示在这个做法中第

i

个背包装的物品总重量

于是可以得到

n

个物品的总重量

T

：

\begin{cases} W(1)+W(2)>1\\ W(3)+W(4)>1\\ \cdots\\ W(2M-1)+W(2M)>1 \end{cases}\Rightarrow T=W(1)+W(2)+\cdots+W(2M)>M

从而无论如何都需要至少

\lceil T\rceil=M+1

个背包才能装下，矛盾

First Fit

依次考虑每个物品，每次从前往后找到第一个能放下它的背包放进去，找不到则新开一个

这个做法的近似比为

1.7

，同时这个上界是紧的

一个改进版本（First Fit Decreasing, FFD）为：在一开始将所有物品按照重量降序排序，然后做正常的 First Fit，这个做法的近似比为

11/9

，同时这个上界是紧的

Best Fit

依次考虑每个物品，每次找到能放入的最满的背包放入，找不到则新开一个

这个做法的近似比也为

1.7

Online Algorithm

对于在线问题，每次输入一个物品，然后需要立即回答将这个物品放入之前哪个背包中，或是新开一个背包

那么上面的做法中，NF，FF，BF 都是可以在线化的，FFD 不能在线化

同时：任何在线算法的近似比都无法低于

5/3

，除非

P=NP

Knapsack Problem

分数背包（fractional version）

问题：假如每种物品以重量

w_i

，单价

p_i

来描述，且物品可以被任意切分成一定重量，在这种情况下装入大小为

W

的背包能得到的最大价值

这个问题是比较容易的，按照单价

p_i

从大到小贪心取物品能放就放即可

01 背包（0-1 version）

问题：假如每种物品以重量

w_i

，价值

p_i

来描述，物品无法切开，在这种情况下装入大小为

W

的背包能得到的最大价值

有两种策略：

按照价值从大到小能放就放
按照性价比（ $p_i/w_i$ ）从大到小能放就放

然后取两种策略得到的结果的较大值，那么这个算法的近似比为

2

（好像没有证明）

另外，如果使用动态规划，那么可以在

O(n\sum w_i)

的时间内求出精确解（注意，这并非多项式时间复杂度，因为

w_i

一项关于输入量不是多项式的）

K-center Problem

问题：给出平面上的

n

个点

p_i

，确定

k

个中心点

q_i

，使得所有点到最近中心点欧几里得距离的最大值最小

换言之，最小化：

\max_{i=1}^n\{\min_{j=1}^k\{\operatorname{distance}(p_i,q_j)\}\}

（这里，距离指的是欧几里得距离，满足对称性，自反性和三角不等式，具有同样性质的距离还有曼哈顿距离）

一个简单版本

这个问题较为困难，不妨先考虑这个版本：

如果已知最优解是 $r$ ，那么能否给出一个半径为 $2r$ 的中心点集构造？

实际上是可以的，如下算法即是：

取出点集中的任意一个点，将这个点作为一个中心点
以这个点为圆心， $2r$ 为半径作圆，删除圆内的所有点
回到第一步，不断重复直到点集被删空

这样构造出的中心点个数一定不超过

k

（解释一下，最优解的一个圆中任意两个点距离

\le 2r

，因此如果一对点在最优解中处于同一个圆中，那么在上面的构造中这一对点也一定可以出现在同一个圆中（只是可以而非一定），从而不可能需要多于

k

个中心点）

从而，如果按照上面的做法构造出多于

k

个中心点了，那么最优解一定

>r

（逆否命题）

回到原问题

回顾上面的做法，实际上第二步取点这里是与

r

有关的，那么能否每次取一个最远的点呢，这样每一步都能 “取到更远的地方，从而一次删掉更多点”，那么修改一下上述做法，把

r

这部分去掉：

取出点集中的任意一个点，把这个点作为第一个中心点
接下来，每次取出与所有中心点最近距离的最大的那个点，将这个点加入中心点集
不断重复操作，直至取出 $k$ 个中心点
构造出所有中心点之后，得到半径 $r'$ ，则有 $r'\le 2r$ ，即这个算法的近似比为 $2$

可以发现这里的第二步与上面做法的第二步起到了同一个效果

这个问题有多难

这个问题没有低于

2

的近似比的做法，除非

P=NP

（证明的话，已经证明了如果存在

(2-\varepsilon)

近似，则可以在多项式时间内解决支配集问题）

另外，如果距离定义不满足三角不等式（非度量 k-center 问题），则这个问题甚至不存在任意常数近似比的做法，除非

P=NP

，不可改进界为

o(\log n)

Local Search

从直觉上理解局部搜索，其实就相当于梯度下降，在一个碗里让小球按重力作用下滑，那么最终小球静止的位置就是一个局部最小值

那么对算法也是如此，每次对当前解做出一个微小的扰动，并选择最优的那个方向递归下去，直到成为邻域中的最优解，此时找到了局部最优解，算法停止（由于局部最优解不一定是全局最优解，因此局部搜索也是近似算法）

Vertex Cover Problem

顶点覆盖问题：给出一张

n

个点

m

条边的无向图，求出一个最小的点集

S

，满足任意一条边都有至少一个端点在

S

中

那么需要界定的内容有：

贡献函数，那么显然一个局面的代价为 $|S|$ ，我们需要最小化这个代价
搜索起点是什么，这里全集显然是一个可行解（但不一定最优），因此从全集开始搜索
如何进行扰动，这里采取从当前点集中删去一个的方法

因此就可以得到一个（实际上很蠢）的做法：

从全局开始，一次遍历点集中的所有点，如果删掉这个点之后依然是顶点覆盖，那么就删去并递归下去

一些改进

基于物理方法的做法有可能表现更好，如模拟退火（Simulated Annealing），其核心在于当扰动到一个更劣的解时，我们依然会以一定的概率接受这个解，同时，这里扰动就是 flip 一个点的状态而非删去一个点了（如果扰动到更好的解，那一定会接受）

Hopfield Neural Networks

问题：给出

n

个点

m

条边的带权无向图，边权

w_e

为正或为负，需要给每个节点设置一个

1/-1

状态，若

w_e>0

则表示希望两端点状态相反，否则表示希望状态相同

由于满足所有边权的限制可能无法做到（若将

w_e<0

的边缩起来之后存在奇环就无解），因此希望找到一个尽量好的解

一个新的问题：

称一条边是好的，当且仅当 $w_ea_ua_v<0$ ，否则是坏的
称一个节点 $u$ 是好的，当且仅当 $\sum_{(u,v)\in E}w_ea_ua_v\le 0$
称一个局面是稳定的，当且仅当所有节点都是好的

那么一个简单的做法：

从全 $1$ （或全 $-1$ 无所谓）开始，每次选中任意一个不好的节点，翻转其状态

这个做法能在有限步内结束吗？可以，这个算法会在至多

\sum|w_e|

步之后结束：

设势函数

\Phi(S)

表示当前局面下所有好的边的边权绝对值之和

那么在翻转一个不好的节点的状态之后：

与其相连的所有边，好边变成坏边，坏边变成好边，因此
$\Phi(S')=\Phi(S)+\sum_{(u,v)\in E}[(u,v){\rm\ is\ bad}]|w_e|-\sum_{(u,v)\in E}[(u,v){\rm\ is\ good}]|w_e|$
又因为这是一个不好的节点，因此后面的增量严格 $>0$ ，因此每次操作完之后 $\Phi(S)$ 严格增大，同时又有上界 $\sum|w_e|$ ，因此一定会结束

如果将上面的分析应用到局部搜索中，就是每次翻转一个状态，最大化最终状态的

\Phi(S)

The Maximum Cut Problem

最大割问题：给出

n

个点

m

条边的带权无向图，将点集分成两个部分，最大化横跨两个部分的边权之和

（最小割问题是容易问题，因为最小割等于最大流）

将每条边的边权都取反，那么一个割的权值就是

\Phi(S)

，那么上一个问题的做法自然可以应用到最大割问题

解有多好？

这个局部搜索算法的近似比为

2

，证明如下：

设

A,B

为该算法分出来的两个点集，

w(A,B)

为割的权值，由于得到的是一个局部最优解，因此对每个

u\in A

，都有：

\sum_{e=(u,v),v\in A}w_e\le \sum_{e=(u,v),v\in B}w_e

那么：

w(A,B)=\sum_{u\in A}\sum_{v\in B}w_{uv}\le \sum_{u\in A}\sum_{v\in A}w_{uv}=2\sum_{\{u,v\}\sube A}w_{u,v}

同理可得

w(A,B)\le 2\sum_{\{u,v\}\sube B}w_{uv}

那么最优解

(A^*,B^*)

就有：

w(A^*,B^*)\le \sum_{e}w_e=\sum_{\{u,v\}\sube A}w_{uv}+\sum_{\{u,v\}\sube B}w_{uv}+w(A,B)\le 2w(A,B)

于是得到近似比为

2

另外：

在 Unique Game Conjecture 下，近似比最好为 $1.1382$
不存在近似比低于 $17/16$ 的算法，除非 $P=NP$

能做到多快？

如果一次扰动能做到比较大的改进才接受：如果一次扰动让答案至少增大了

\dfrac{2\varepsilon}{|V|}w(A,B)

那么才接受，在这种做法下，可以做到

(2+\varepsilon)

的近似比，同时算法会在至多

O(\dfrac{n}{\varepsilon}\log W)

步后结束

更大的邻域？

可能在一次扰动翻转多个节点的状态

Randomized Algorithms

随机的对象是？

输入数据随机，这种情况下我们通常需要分析平均情况（average case）
算法的行为随机，即 “随机算法”
- 高效的确定性算法可以认为是随机算法的一个特殊情况，一般来说：
- 蒙特卡洛算法：高效，同时只需要以较高的正确率得到答案的算法
- 拉斯维加斯算法：正确，同时只需要以较好的期望时间运行完毕的算法（最坏情况可能很差）
- 通常在没有高效确定性算法的情况下，正确率和效率是不能得兼的

Hiring Problem

问题：

有

n

个面试者，用能力值

a_i

描述，先希望从

n

个面试者中雇佣

1

位

其中，面试成本为

C_I

，雇佣成本为

C_H

，且

C_I

远小于

C_H

现在希望平衡总成本与雇佣到的面试者的能力

一个最直接的做法

按顺序面试所有人，并维护目前能力值最大值
在新来了一个人后：
- 若其能力值大于目前最大值，则雇佣（之前那个被自动解雇了）
- 否则，不雇佣

这个做法的有点在于一定能雇佣到能力值最大的人，但是总成本在

a_i

单增的情况下最坏可以达到

O(nC_H)

（

C_I

一项忽略了）这是不可接受的

如果将面试顺序打乱？

考虑

n

个人随机重排之后使用上面的做法，那么成本分成两个部分：

面试成本，这部分无法避免，为 $O(nC_I)$
雇佣成本，假设最终雇佣了 $m$ 次，则为 $O(mC_H)$

现在只需要计算

m

的期望，同时由线性性，

m

的期望可以转化为每个人被选中的期望，这里

n

个人进行了随机重排，那么位于位置

i

的人被选中（即其为

1\sim i

中的最大值）的概率为

\dfrac{1}{i}

，于是

E(m)=\sum_{i=1}^n\dfrac{1}{i}=\ln n+O(1)

最终总成本为

O(nC_I+\ln n\cdot C_H)

，也能雇佣到能力最强的人，同时期望成本大大降低（最坏情况还是很差（即随机到单增序列这种逆天情况），但是几乎不发生）

Online Hiring Problem

内容同上，但是这里只能雇佣一次（在这种情况下，总成本不考虑，只考虑雇佣到的人的能力）

此时我们的做法是将所有人先随机重排，然后取前

k

个人的最大值

A

，再遍历后面

n-k

个人，雇佣第一个遇到的

\ge A

的人即可

然后需要分析

k

的取值，即雇佣到最大值的概率

设雇佣到了位置

i

，且其确实是最大值的概率为

P(i)

，那么有两个条件：

位置 $i$ 确实是最大值，概率为 $1/n$
$k+1\sim i-1$ 都没有被雇佣，换言之， $1\sim i-1$ 中的最大值出现在 $1\sim k$ 中，概率为 $k/(i-1)$
因此 $P(i)=\dfrac{k}{n(i-1)}$

那么雇佣最大值的概率为

\sum_{i=k+1}^nP(i)\approx \dfrac{k}{n}\ln \dfrac{n}{k}

对

k

求极值，得到

k=n/e

，此时概率为

1/e

是最大值

Quicksort

确定性快速排序：

期望情况（即输入数据随机）为 $\Theta(n\log n)$
最坏情况（即每次递归规模减一）为 $\Theta(n^2)$

引入随机化思想，每次随机一个 pivot

定义 Central splitter：若一个 pivot 将规模为

n

的原问题分为两半，其中每一半都至少是

n/4

，则成这个 pivot 是一个 central splitter

那么显然有一半的数字都是 central splitter，因此期望递归两层就能找到，一旦找到，最坏情况也是分为

n/4

与

3n/4

的两个部分，在取对数意义下时间复杂度依然是

\Theta (n\log n)

Parallel Algorithms

背景：有多个处理器可以同时运行，同时对一个共享的数据空间进行读写

那么在资源上可能产生冲突，于是出现了以下几种模式：

Exclusive-Read Exclusive-Write (EREW)：即同一时刻读和写都只能由一个处理器执行
Concurrent-Read Exclusive-Write (CREW)：即同一时刻允许多个处理器读，但只允许一个处理器写
Concurrent-Read Concurrent-Write (CRCW)：即同一时刻允许多个处理器读写
- Arbitrary rule：从哪个处理器写入是任意的
- Priority rule：按某种优先级选择处理器写入
- Common rule：只有当所有处理器写入的值相同时才写入

Summation Problem

按照线段树的方式执行求和，一层一层往上做，每一层中的所有加法并行执行

其中

B(h,i)

为线段树节点编号，

h

为节点所在深度，叶子为

0

，向上递增，

i

为同层编号，从左往右从

1

开始

那么显然

B(h,i)=B(h-1,2i-1)+B(h-1,2i)

，且

B(0,i)=A(i)

衡量处理器数量与运行时间的方式

定义：

设 $T_p$ 表示在有 $p$ 个处理器时算法的运行时间，在接下来的讨论中，我们只关心两个特殊情况 $T_1,T_\infty$
设工作量（work） $W$ 为整个算法执行的单位操作的个数
设深度（depth） $D$ 表示求解过程中的最长链

那么显然：

T_1=W,T_\infty=D

，对于处于中间值的

p

，其

T_p

往往较难分析（与具体算法有关），但有以下关系：

\dfrac{W}{p}\le T_p\le \dfrac{W}{p}+D

（粗略理解就是将整个算法执行的单位操作拓扑排序，然后按

p

个一组来做，这样一共要做

W/p

轮，其中每一层由于上取整会多出来一个不满

p

个的组产生额外

1

的贡献，因此下界与上界差了

D

）

回到 Summation Problem，对上面的做法，就有

W=\Theta(n),D=\Theta(\log n)

Prefix-Sums

问题：给出序列

A(1),A(2),\cdots ,A(n)

，计算所有前缀和

C(i)=A(1)+A(2)+\cdots +A(i)

那么设：

$B(h,i)$ 表示该节点对应区间内所有数的和
$C(h,i)$ 表示 $i$ 在 $h$ 级祖先对应区间内的前缀和

于是在合并两棵子树

(h-1,2i-1),(h-1,2i)

时：

$B(h,i)=B(h-1,2i-1)+B(h-1,2i)$ 与上面相同
左侧子树内的下标 $j$ ： $C(h,j)=C(h-1,j)$
右侧子树内的下标 $j$ ： $C(h,j)=C(h-1,j)+B(h-1,2i-1)$

初始情况为

B(0,i)=C(0,i)=A(i)

，显然每一层的处理都可以并行做

这样

W=\Theta(n),D=\Theta(\log n)

归并

问题：给出两个有序的序列

A(1\cdots n),B(1\cdots n)

，希望将它们合并成一个有序的序列

C(1\cdots 2n)

（这里假设

A(i),B(i)

两两不同，若不满足，则可以额外添加一维关键字）

传统归并必须按顺序比较

A,B

中的数字，几乎无法并行，因此从另一个方向入手：找到

A(i),B(i)

合并后的排名

设

rk(A,i)

为

B

中比

A(i)

小的数字个数，

rk(B,i)

同理

那么合并过程即为：

CPP

for i=1 to n pardo
	C(i+rk(A,i)):=A(i)
for i=1 to n pardo
	C(i+rk(B,i)):=B(i)

现在考虑能否并行解决排名求解问题

Parallel Ranking

两个最直接的做法

按照传统方式求 rk，此时相当于按传统方式归并，因此 $W=D=\Theta(n)$
并行执行 $n$ 次二分查找，此时 $W=O(n\log n),D=O(\log n)$

Partitioning

对 $A,B$ 序列都做一次：
- 按 $\log n$ 的间隔取数，即取出 $A(1),A(1+\log n),A(1+2\log n),\cdots$ 一共 $n/\log n$ 个数，序列 $B$ 同理
- 这一部分数用上面并行二分查找的方式求解，此时 $W=n/\log n\times \log n=O(n),D=O(\log n)$
那么每个序列，自己本身划分成了若干大小为 $\log n$ 的段，又通过另一个序列的二分查找产生了 $n/\log n$ 个断点，这样 $A,B$ 均被至多划分为 $2n/\log n$ 个段，同时各段之间存在对应
接下来，每一段内部的数用传统循环的方式求解 rk，此时 $W=n/\log n\times \log n=O(n),D=O(\log n)$
- 解释一下，一共有 $2n/\log n$ 个段，每个段循环求解，时间为该段的长度，即 $O(\log n)$

Maximum Finding

问题：求出

n

个数的最大值

两个最直接的做法

显然这个东西可以复用 Summation Problem 的做法，把所有的加法操作换成 $\max$ 即可，这样不难做到 $W=O(n),D=O(\log n)$ ，但是这种做法忽略了一个性质： $\max$ 运算允许内容重叠但加法不允许
并行所有 $\operatorname{pair}(i,j)$ 的大小比较，然后并行检查每个数是否存在比它大的数，这样 $W=O(n^2),D=O(1)$
- 解释一下，这里当 $A(i)<A(j)$ 时将 $B(i)$ 置 $1$ ，这里可能存在同时写入的情况，但是是允许的（Common rule，写入的值都是 $1$ ）

稍微优化一下

将

A(1\cdots n)

划分为

\sqrt n

个部分，每个部分包含

\sqrt n

个数，然后应用上面的做法，这样

每递归一层，序列长度开根号
每一层中并行执行所有比较：
- $T(n)=\sqrt n\cdot T(\sqrt n)+O(1)\Rightarrow T(n)=O(\log \log n)$
- $W(n)=\sqrt n\cdot W(\sqrt n)+O(n)\Rightarrow W(n)=O(n\log\log n)$

这样就稍微优化了一下上面的做法

再稍微优化一下（Doubly-logarithmic Paradigm）

做两步：

将序列划分为 $n/h$ 个部分，每个部分包含 $n/h$ 个数
每个部分用上面的做法来做， $T(n)=O(\log\log \dfrac{n}{h}),W(n)=O(h\times \dfrac{n}{h}\log\log \dfrac{n}{h})=O(n\log\log \dfrac{n}{h})$
现在得到了 $n/h$ 个数，再按上面的做法来做， $T(n)=O(\log\log \dfrac{n}{h}),W(n)=O(\dfrac{n}{h}\log\log \dfrac{n}{h})$

于是

h

取

\log\log n

，就可以做到：

T(n)=O(\log\log n),W(n)=O(n)

一个随机化做法（Random Sampling）

在期望意义下表现非常好，分成以下几步：

从序列 $A$ 中随机取出 $n^{7/8}$ 个数形成序列 $B$
将序列 $B$ 划分为 $n^{3/4}$ 个部分，每个部分包含 $n^{1/8}$ 个数，然后对每个部分使用 $W=O(n^2),D=O(1)$ 的做法，则总共为： $W=n^{3/4}\times (n^{1/8})^2=O(n),D=O(1)$
这样序列 $B$ 长度就缩小为 $O(n^{3/4})$ 了，将 $B$ 划分为 $n^{1/2}$ 个部分，每个部分包含 $n^{1/4}$ 个数，对每个部分使用同样的做法，总共为 $W=n^{1/2}\times(n^{1/4})^2=O(n),D=O(1)$ ，于是就找到了 $B$ 中的最大值 $M$
接着暴力遍历 $A$ 中没有放入 $B$ 的数，如果存在数 $>M$ ，则将所有这些数字随机替换掉序列 $B$ 中的数，并回到第二步重新做一轮，直到不存在数 $>M$ 为止

可以证明，每一轮均为

W=O(n),D=O(1)

，同时期望轮数是常数，因此最终为

W=O(n),D=O(1)

External Sorting

背景：

要对非常大规模的数据进行排序
访问速度快的内存不够大
硬盘容量大，但只有在按顺序访问时较快，随机访问的开销极大

定义

Record：单个数据

Run：有序段（即一系列已排好序的数据）

Tape：磁带（即若干分立的存储空间）

Pass：归并排序的总轮数

设总数据规模为

n

，内存能容纳的数据规模为

m

一个最简单的做法（两路归并，4-tape）

所有数据初始存储于 $T_1$ 磁带中，然后以 $m$ 个一组载入内存中，用任意其他排序算法在内存中排好序，形成一个 run，并以 $2,3,2,3\cdots$ 的顺序加入到其他 tape 中
接下来每一轮，每次取出所有 tape 的第一个 run 进行归并，形成一个更长的 run，并用与上相同的方式加入到空闲的 tape 中，知道只剩下一个 run，此时排序完成

其中第

1

步也算一个 pass，那么第

1

步结束后有

n/m

个 run，第二步每一轮 pass 完成后单个 tape 上的 run 个数减半

因此总 pass 轮数为

1+\lceil \log_2(n/m)\rceil

优化： $k$ 路归并

但是直接按照上面的方式，需要

2k

个 tape，继续优化

考虑按照斐波那契数列对所有 run 进行划分：

CPP

 0  0 34 (split 34 to 21+13)
21 13  0 (13 run from 1,2 to 3)
 8  0 13 ( 8 run from 1,3 to 2)
 0  8  5 ( 5 run from 2,3 to 1)
 5  3  0 ( 3 run from 1,2 to 3)
 2  0  3 ( 2 run from 1,3 to 2)
 0  2  1 ( 1 run from 2,3 to 1)
 1  1  0 ( 1 run from 1,2 to 3)
 0  0  1 (finish)

这样就用

3

个 tape 完成了

2

路归并（如果初始 run 个数不是斐波那契数则补到最近的）

那么

k

路归并就只需要使用高阶的斐波那契数列即可

F_n^{(k)}=\sum_{i=1}^kF_{n-i}^{(k)}

同时只需要使用

k+1

个 tape

优化：并行

结论：如果要并行进行

k

路归并，则需要将内存划分为

2k

个输入缓冲区和

2

个输出缓冲区

（大意可能是一半处理一半输入/输出，这样同时进行）

优化：生成更长的 run

容易想到，如果初始 run 长度

\ge m

，那么 run 个数就会少，pass 也会减小，那么采用 replacement selection 算法：

维护一个大小为 $m$ 的小根堆以及当前 run 的最后一个数 $X$ ，初始将前 $m$ 个数加入堆中
弹出未打标记的最小值，加入至 run 并更新 $X$ $X$ ，加入一个新的数 $Y$ $Y$
- 若 $Y\ge X$ ，那么说明 $Y$ 也可以放在这个 run 中，不打标记正常加入堆中即可
- 若 $Y<X$ ，那么将 $Y$ 加入到堆中并打上一个标记，如果此时堆中打过标记的元素个数达到了 $m$ ，则新开一个 run

在序列初始已经基本有序的情况下，这种方法往往非常有效

（相当于维护了两个堆，一个堆存储能放在同一个 run 里的，另一个存储不能的，每次取出第一个堆的堆顶，然后加入一个数就看一下大小关系来确定放在哪个堆里，当第一个堆弹空了就新开一个 run，并交换一下两个堆）

优化：缩短合并时间

对

k

路归并，使用哈夫曼编码的方式进行合并（每次合并最短的两个 run）

文章操作

AVL Tree

插入

删除

性质维护

Splay Tree

旋转操作：Splay

插入操作

删除操作

Inverted File Index

Leftist Heaps

合并操作

递归版本

迭代版本

删除操作

Skew Heaps

合并操作

递归版本

迭代版本

复杂度分析

Backtracking

Eight Queens

Turnpike Reconstruction Problem

Tic-tac-toe（井字棋）

Minimax Strategy

α−β\alpha-\betaα−β pruning

NP-Completeness

什么是算法？

不可判定问题（Undecidable Problems）

两种图灵机（Turning Machine）

确定性图灵机（Deterministic Turing Machine）

非确定性图灵机（Nondeterministic Turing Machine）

NP: Nondeterministic Polynomial-time

两类问题的关系

NPC: NP-Complete

第一个 NPC 问题

一个例子

NPH: NP-Hard

一个例子

Approximation Algorithms

近似比

近似方案

Polynomial-time approximation scheme（PTAS）

Bin Packing Problem

Next Fit

First Fit

Best Fit

Online Algorithm

Knapsack Problem

分数背包（fractional version）

01 背包（0-1 version）

K-center Problem

一个简单版本

回到原问题

这个问题有多难

Local Search

Vertex Cover Problem

Hopfield Neural Networks

The Maximum Cut Problem

解有多好？

能做到多快？

更大的邻域？

Randomized Algorithms

Hiring Problem

一个最直接的做法

如果将面试顺序打乱？

Online Hiring Problem

Quicksort

Parallel Algorithms

Summation Problem

衡量处理器数量与运行时间的方式

Prefix-Sums

归并

Parallel Ranking

两个最直接的做法

Partitioning

Maximum Finding

两个最直接的做法

稍微优化一下

再稍微优化一下（Doubly-logarithmic Paradigm）

$\alpha-\beta$ pruning

优化： $k$ 路归并