前言#

本章将系统复习《算法导论》中的一些经典问题，主要包含如下内容：

动态规划——最优二叉搜索树
基本图论——BFS，DFS
单源最短路——Bellman-Ford 算法, Dijkstra 算法
最大流——Ford-Fulkerson 方法，Edmonds-Karp 算法
散列表——开放定址法（双散列）
贪心算法——哈夫曼编码
堆排序
线性时间排序

本篇主要以例题为主，不会过多介绍基础知识及其推导过程。如果对某个分类感兴趣的话，欢迎阅读其他子分篇。

点我前往归档页面：https://hoyue.fun/categories/学习笔记/算法设计与分析

PS：这里不包括分治法及其之前的内容，具体请见各自章节。

动态规划——最优二叉搜索树#

本部分对应分篇：【算法设计与分析】动态编程

普通的二叉搜索树 (BST) 的查询效率取决于树的高度。但在现实中，我们查找每个关键字 (Key) 的频率是不一样的。比如在一个字典里，查找 “the” 的频率远高于 “xylophone”。

我们希望查找频率高的节点离根节点更近，从而使 期望搜索代价 (Expected Search Cost) 最小化。

如果一棵树是最优的，那么它的左子树和右子树也必须是关于它们各自包含的关键字的最优二叉搜索树。

对于节点来说，我们有：

关键字 (非叶子节点) $K = ⟨ k_{1}, \dots, k_{n} ⟩$ ：有序的实际数据。对应概率 $p_{i}$ 。
伪关键字 (叶子节点) $D = ⟨ d_{0}, \dots, d_{n} ⟩$ ：代表落在关键字之间的区间（搜索失败的情况）。对应概率 $q_{i}$ 。

给定一个包含 n 个不同的键的集合 $K = {k_{1}, k_{2}, \dots, k_{n}}$ 以及这些键对应的 成功查找概率 $p_{1}, p_{2}, \dots, p_{n}$ 和 失败查找概率 $q_{1}, q_{2}, \dots, q_{n}$ 。我们要构造一个二叉搜索树 (BST)，使得树的 加权查找成本最小。

e table: e[i, j] 为在包含键 $k_{i}, \dots, k_{j}$ 的最优二叉搜索树中进行一次关键字搜索的 期望代价 。
w table: w[i, j] 为包含关键字 $k_{i}, \dots, k_{j}$ 的子树的 总概率（即子树中 所有键的概率之和 (包含 $p$ 和 $q$ )）。
root table: root[i, j] 表示构成子树 $k_{i}, \dots, k_{j}$ 的 根节点。

动态规划的状态转移过程如下：

建议先对 $p$ 值表和 $q$ 值表 计算其概率和 $p_{i} + q_{i}$ 以便后续使用。
初始化时，首先处理只有伪关键字的情况（空树）。对 $i = 1 \dots n + 1$ ：
- $e [i, i - 1] = q_{i - 1}$
- $w [i, i - 1] = q_{i - 1}$
迭代填表：我们要计算长度 $l = 1, 2, \dots, n$ 的所有情况。有两层循环来迭代：
1. 外层循环： $l$ (链长) 从 1 到 $n$ 。
2. 内层循环： $i$ (起始点) 从 1 到 $n - l + 1$ 。
3. 计算 $j$ ： $j = i + l - 1$ (终点)。
对于每一个单元格 $(i, j)$ ，我们做以下操作：
1. 计算 $w [i, j]$ ：利用公式 $w [i, j] = w [i, j - 1] + p_{j} + q_{j}$ (利用已有的 $p_{i} + q_{i}$ 值，不用每次累加)。
2. 根据 $w$ 表寻找最佳根 $r$ ：遍历 $r$ 从 $i$ 到 $j$ ，
  1. 计算临时代价 $t = e [i, r - 1] + e [r + 1, j] + w [i, j]$ 。
  2. 找到最小的 $t$ ，存入 $e [i, j]$ 。
  3. 记录对应的 $r$ 存入 $roo t [i, j]$ 。

下面是一个例子：

概率表：

我们先从 $w$ 表开始，它的公式为：

w [i, j] = {q_{i - 1} w [i, j - 1] + p_{j} + q_{j} if j = i - 1 if i \leq j

填表有如下规律：

首先先填对角线，填入 $q_{i}$ 的所有内容。
然后再填已填写位置右侧的一格（例如已填写 w[1,0], 那么接下来就填 w[1,1]），它的内容根据公式等于 左侧单元格内容 + 当前列号(j)对应的 $p_{j}$ 和 $q_{j}$ 的概率和 。
这是一个斜向右填表的过程，如果已经到达右边的边上，则不用填。每次要填写的数据都少一个（即第一次填6个，第二次就填5个，因为最后那个已经到达边上）。

i\j	0	1	2	3	4	5	6	7
1	0.06	0.16	0.28	0.42	0.49	0.64	0.81	1.00
2		0.06	0.18	0.32	0.39	0.54	0.71	0.90
3			0.06	0.20	0.27	0.42	0.59	0.78
4				0.06	0.13	0.28	0.45	0.64
5					0.05	0.20	0.37	0.56
6						0.05	0.22	0.41
7							0.05	0.24
8								0.05

注意检查右上角的值一定为1！

接下来是 $e$ 表和 $roo t$ 表， $e$ 表的公式为：

e [i, j] = {q_{i - 1} min_{i \leq r \leq j} {e [i, r - 1] + e [r + 1, j] + w (i, j)} if j = i - 1 if i \leq j

填表有如下规律：先填主对角线 ( $l = 1$ )，再填上面一条 ( $l = 2$ )，最后右上角的 $e [1, n]$ 就是我们最终的最小期望代价。

首先也是对角线的值为 $q_{i}$ ；
之后的值中， r 的取值有 j-i 种，需要每个讨论 j-i 次，取其讨论的最小值。
每次讨论等价于对位相加。例如第 1 次讨论则是 $e$ 表中这一行的第 1 个数 + $e$ 表中这一列的第 1 个数 + $w$ 表中该位置的值。即 对于 e[i,j] 的第 $k (k \in [i, j])$ 次讨论，为该行（第i行）的第k个数 + 该列（第j列）的第k个数 $+ w [i, j]$ 。
对于讨论中相同的值，选择讨论次数 k 最小的，因为替换最小值时比较为 < 而不是 ≤。
这个过程也是斜向右填表，越往后的讨论次数越多。

例如，对于第 $(1, 3)$ 位置上的 $e$ 值，算出它的所有讨论：

$r = 1 : e (1, 0) + e (2, 3) + w (1, 3) = 0.06 + 0.68 + 0.42 = 1.16$
$r = 2 : e (1, 1) + e (3, 3) + w (1, 3) = 0.28 + 0.32 + 0.42 = 1.02$
$r = 3 : e (1, 2) + e (4, 3) + w (1, 3) = 0.62 + 0.06 + 0.42 = 1.10$

选择最小的 $1.02$ 作为 $e [1, 3]$ 。我们需要记住这个选项选的是 $r = 2$ 的情况，它将成为该位置的 $roo t$ 值。

i\j	0	1	2	3	4	5	6	7
1	0.06	0.28	0.62	1.02	1.34	1.83	2.44	3.12
2		0.06	0.30	0.68	0.93	1.41	1.96	2.61
3			0.06	0.32	0.57	1.04	1.48	2.13
4				0.06	0.24	0.57	1.01	1.55
5					0.05	0.30	0.72	1.20
6						0.05	0.32	0.78
7							0.05	0.34
8								0.05

对于root表，它的行和列均为 $1 \dots n$ ，也是从对角线开始填。右上角为整个树的根。

我们在计算 $e$ 值表的时候，就需要记录对应的 $r$ 存入 $roo t [i, j]$ 。例如之前的例子中 $r = 2 ⟹ roo t [1, 3] = 2$ 。

root表：

i\j	1	2	3	4	5	6	7
1	1	2	2	2	3	3	5
2		2	3	3	3	5	5
3			3	3	4	5	5
4				4	5	5	6
5					5	6	6
6						6	7
7							7

我们已经画出了 $roo t$ 表，接下来我们利用 $roo t$ 表进行递归构建得到最优二叉搜索树。

我们要知道： $roo t [i, j]$ 告诉我们在范围 $k_{i} \dots k_{j}$ 中，谁是 老大（根）。

构建的过程：

找主根 (Main Root)：对于一个计算好的 $roo t$ 表，范围是 $1 \dots n$ 。例如我们这题的例子中范围是 $1 \dots 7$ ，那么主根就是 $roo t [1, 7] = k_{5}$
构建左子树：我们已经找到了主根为 $k_{r} = k_{5}$ ，那么它的左子树的范围是 $k_{1} \dots k_{r - 1}$ 即 $k_{1} \dots k_{4}$ 。我们开始查找这个范围的根为 $roo t [1, r - 1] = roo t [1, 4] = k_{2}$ ，左子树的根为 $k_{2}$ 。
构建右子树：同理，它右子树的范围是 $k_{r + 1} \dots k_{n}$ 即 $k_{6} \dots k_{7}$ 。我们开始查找这个范围的根为 $roo t [r + 1, n] = roo t [6, 7] = k_{7}$ ，右子树的根为 $k_{7}$ 。
递归深入：我们对构建好的左右子树再递归应用上述的 (2) 和 (3)，直到该根没有子节点为止。例如， $k_{2}$ 的左子树查找 $roo t [1, 1] = k_{1}$ ，但对于 $k_{1}$ 而言，当前的 $r_{1} - 1 = 1 - 1 = 0$ 已经不存在了，就终止了。对于右子树同理，如果查到的范围是 $roo t [i, i - 1]$ 时终止。
处理伪关键字：在构建完根节点后，开始 从左向右 为那些根节点挂上叶子节点，并从 $0$ 开始顺序编号。

最后根据这个表，生成一个树如图：

基本图论#

本部分对应分篇：【算法设计与分析】基础图论算法

BFS#

BFS 的搜索过程是一层一层向外的，就犹如水波(wave)一样。BFS 就是这样，先访问距离 $s$ 为 1 的所有节点，再访问距离为 2 的… 以此类推。

简单来说，对于BFS的过程如下：

从 $s$ 开始，一层一层地发现顶点。
首先访问距离 $s$ 只有 1 条边的所有顶点 ( $s$ 的下一层)。
从那些顶点开始，访问距离下一层的所有顶点，以此类推。
直到它发现了从 $s$ 出发可到达的每个顶点。

BFS 使用先进先出的队列 $Q$ 来管理灰色节点，从而保证了“层级”顺序。用下列的值表示中间过程：

$v . d$ (Distance): 从源点 $s$ 到 $v$ 的距离（边数）。
$v . π$ (Predecessor): 前驱节点，用于回溯路径。

我们通过一个例子来进一步掌握：

对于如下的图，设从 s 出发，求以字典序的 BFS 中，每个顶点的 $d$ 值表、 $π$ 值表和队列出队顺序 $Q$ 。

遍历与 s 相邻的节点，并把 s 出队，那些节点按照字典序入队，给它们的 d 赋值 1，π 赋值为 s。此时队列 $Q : {r, u, v}$ ；
接下来 r 出队，并把其相连的 t 和 w 入队，并给它们d = 2，π = r， $Q : {u, v, t, w}$ ；
u 出队，并把其相连的且没有被访问过的y入队，并给它d = 2，π = u， $Q : {v, t, w, y}$ ；
v 出队，与它相邻的均以入队， $Q : {t, w, y}$ ；
t 出队，与它相邻的均以入队或已经出队， $Q : {w, y}$ ；
w 出队，并把其相连的且没有被访问过的 x 和 z 入队，并给它们 d = 3，π = w， $Q : {y, x, z}$ ；
y 出队，与它相邻的均以入队或已经出队， $Q : {x, z}$ ；
x 出队，与它相邻的均以入队或已经出队， $Q : {z}$ ；
z 出队，与它相邻的均以入队或已经出队， $Q : {\emptyset}$ ；

把这个过程整合成表格得：

	r	s	t	u	v	w	x	y	z
v.d	1	0	2	1	1	2	3	2	3
v.π	s	NIL	r	s	s	r	w	u	w

这个过程中队列的变换： $Q : {s, r, u, v, t, w, y, x, z}$

DFS#

DFS 则是先探索一条道路到头，再回溯到分叉口进行其他探索。

与 BFS 不同的是，DFS 必须访问所有的顶点 ，所以可能深度优先搜索有多个源点。还有广度优先搜索的前驱子图是一棵树，但是深度优先搜索的前驱子图可能包含若干棵树，这是由于搜索可能从多个源点进行。

DFS 不像 BFS 那样依赖显式的队列，而是通过递归 (Recursion) 隐式地使用栈 (Stack)。

除了之前 BFS 的 d 外，深度优先搜索还给每个顶点加时间戳(timepstamp)。

每一个顶点 $v$ 有两个时间戳：

第一个时间戳 $v . d$ 记录了 $v$ 第一次被发现的时间 (discovery time);
第二个时间戳 $v . f$ 记录了 $v$ 被搜索结束的时间 (finish time)，即 $v$ 的邻接表全部检查完。

显然， $v . d < v . f$ 。

简单来说，DFS 的过程如下：

初始化: 所有结点染白（表示未访问过）。时间 $t im e = 0$ 。
主循环: 对图中的每个结点 $u$ ，如果是白色，则调用 DFS-VISIT(u)。所以，在结束联通结点之后，会再次对白色结点调用 DFS-VISIT(u)。这保证了即使图是不连通的，DFS 也能遍历所有结点，生成“深度优先森林”。
DFS-VISIT(u):
1. $t im e = t im e + 1$ 。 $u . d = t im e$ ，并将 $u$ 染灰（第一次访问到）。
2. 对于 $u$ 的每个邻接点 $v$ ：如果 $v$ 是白色，递归调用 DFS-VISIT(v)，直到邻接的点没有白色为止。
3. 将 $u$ 染黑。 $t im e = t im e + 1$ 。 $u . f = t im e$ 。

例如下面的这个例子：

如图，以字典序进行 DFS 搜索，输出一个 $d$ 表和 $f$ 表。

以字典序的 DFS，那么我们应该以 q 开始，因为它字典序最小。
按照字典序，先走 s 这条路径，一路走到： $q \to s \to v \to w$ ，此时走到头了，一直回溯到分叉口 q 处。此时有： q: 1/? s:2/7 v:3/6 w:4/5. q的 f 为 ? 是因为还有一个箭头指向它，可能之后还有访问到，f 记录的是最后访问的时间戳。
接着沿着 t 这条路径走，根据字典序选择 x 这边： $q \to t \to x \to z$ ，走到头了回溯到分叉口 t，此时有：q: 1/? t:8/? x:3/12 z:10/11。接着往 y 处走： $t \to y \to q$ ，整条路径为： $q \to t \to x \to z \to z \to x \to t \to y \to y \to t \to q$ ，于是有：q: 1/16 t: 8/15 x:9/12 z:10/11 y:13/14
左半部分遍历完了，接下来根据字典序，找到没有被遍历的最小字母 r，走 u这条路径，有：r:17/20 u:18/19

输出为表格得：

这整个过程的遍历图为：

单源最短路#

本部分对应分篇：【算法设计与分析】单源最短路算法

这里简单复习一下所有的最短路径算法的问题模型：

对于图 $G = (V, E)$ 中的每个顶点 $v$ ，我们需要维护两个属性：

$v . d$ ：从源点 $s$ 到顶点 $v$ 的 最短路径 估计 (shortest-path estimate)。初始化时， $s . d = 0$ ，其他所有 $v . d = \infty$ 。
$v . π$ ：顶点 $v$ 在最短路径上的 前驱节点 (predecessor)。

最短路的问题是：一个带权有向图 $G = (V, E)$ ，边权函数 $w : E \to R$ ，给定源点 $s \in V$ ，要找出对所有 $v \in V$ 的最短路径距离。

松弛操作 (relex) 是用来测试是否可以通过边 $(u, v)$ 找到一条到达 $v$ 的更短路径。如果是，这就叫做“松弛”了这条边，并更新 $v . d$ 和 $v . π$ 。

1
RELAX(u, v, w)
2
    if v.d > u.d + w(u, v)
3
        v.d = u.d + w(u, v)
4
        v.π = u

1
        u.d
2
    s ----→ u
3
            |
4
            | w(u,v)    u.d + w(u,v) < v.d ?
5
            ↓
6
    s - - → v
7
        v.d

Bellman-Ford 算法#

Bellman-Ford 算法解决的是一般情况下单源最短路径问题，边的权重可以为负值，给定源点为 s 的有向带权图 $G = (V, E)$ 和权重函数 $w$ ，Bellman-Ford 算法返回一个布尔值，该布尔值表明是否存在一个从源点可达的负权重的环路。

若存在这样一个环路 (有负权重的环路)，则算法提示不存在解决方案(False)。若不存在这样一个环路，则算法给出最短路径和它们的权重(True)。

算法的思路为：

初始化将所有 $v . d$ 设为 $\infty$ ， $s . d$ 设为 0。
按照一定的顺序进行 V - 1 次遍历，每次遍历对图中的每一条边 $(u, v) \in E$ ，执行 RELAX(u, v, w)。
遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路 (FALSE) 否则为 TRUE。

Bellman-Ford 算法的复杂度：

时间复杂度： $O (V E)$ 。因为外层循环 $∣ V ∣$ 次，内层遍历所有边 $∣ E ∣$ 。
空间复杂度： $O (V)$ 。

下面是一个例子：

如果设 s 为源点，按照如下顺序 (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y) 松弛边的话，如下图，找出每个节点的 $d$ 值(最短路长) 和 $π$ 值(前驱节点) 的表格。

首先，通过 INITIALIZE-SINGLE-SOURCE 操作，将所有顶点的 $d$ 值设置为 ∞， $π$ 值设置为 NIL。设置源点 s.d = 0.
第一次循环：从 s 出发，按照顺序遍历这些节点，此时根据 (s, t), (s, y)，我们可以把 t 和 y 的值设置：t.d = 6, t.π = s; y.d = 7, y.π = s。
第二次循环：根据顺序有 (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y) ，通过松弛这些边依次得到：x.d = 11, x.π = t; z.d = 2, z.π = t; x.d = 4, x.π = y。
第三次循环中，在松弛边 (x, t) 时，t.d = 2, t.π = x。
在算法的最后一个步骤中，再进行一次遍历，在松弛边 (t, z) 时，z.d = -2, z.π = t；在松弛边 (z, x) 时，x.d = 2, z.π = z。
这个结果导致某些节点有更短的路径，则存在负权边，返回 FALSE，验证：因为在松弛边 (t, z) 时，z.d = -2, z.π = t；在松弛边 (z, x) 时，x.d = 2, z.π = z。此时负权环为(t, z), (z, x), (x, t) 边组成。

整合成表得：

$d$ 值表：

t	x	y	z
∞	∞	∞	∞
6	∞	7	∞
6	4	7	2
2	4	7	2
2	2	7	-2

$π$ 值表：

s	t	x	y	z
NIL	NIL	NIL	NIL	NIL
NIL	s	NIL	s	NIL
NIL	s	y	s	t
NIL	x	y	s	t
NIL	x	z	s	t

因为再次循环产生了负权环，所以算法返回 FALSE。

Dijkstra 算法#

Dijkstra 算法解决了加权有向图上的单源最短路径问题，但它要求所有边的 权重是非负的 。本质是一个贪心算法 (greedy)：每次从“尚未确定”的点中挑一个目前距离最小的“锁定”。

Dijkstra 维护一个集合 $S$ ，包含那些已经找到最终最短路径的顶点。算法重复从 $V - S$ 中选择当前 $d$ 值最小的节点 $u$ ，将其加入 $S$ ，并松弛从 $u$ 出发的所有边。

初始化：所有 $v . d = \infty, s . d = 0$ 。建立一个最小优先队列 $Q$ ，包含所有顶点（以 $d$ 值作为 key）。
循环：当 $Q$ 不为空时：
1. Extract-Min：从 $Q$ 中取出 $d$ 值最小的顶点 $u$ 。
2. 加入集合：将 $u$ 标记为已处理（加入 $S$ ）。
3. 松弛邻居：对 $u$ 的每一个邻接点 $v$ ：执行 RELAX(u, v, w)。如果松弛成功， $v . d$ 变小了，需要更新 $Q$ 中 $v$ 的位置。

Dijkstra 的效率很大程度上取决于优先队列 (Priority Queue) 的实现方式 $O (E l g V)$ ，所以复杂度就不在此处讨论。

下面是一个例子：

如下图，若我们以 z 为源点，找到所有顶点在算法过程中的 $d$ 值(最短路长) 和 $π$ 值(前驱节点) 表格，以及集合 S 表示的最短路径。

首先，通过 INITIALIZE-SINGLE-SOURCE 操作，将所有顶点的 $d$ 值设置为∞， $π$ 值设置为NIL，S为Ø。设置源点z.d = 0，建立优先队列 $Q = {s, t, x, y, z}$ ，值为它们的 $d$ 值。
接下来，z 出队，更新 s 和 x 的值：s.d = 3, s.π = z；x.d = 7，x.π = z；此时最短路集合S = z。
s 出队，更新值为：t.d = 6, t.π = s；y.d = 8, y.π = s，此时最短路集合S = z, s。
t 出队（它的权比 x 小），无事发生，此时最短路集合S = z, s, t。
x 出队，无事发生，此时最短路集合S = z, s, t, x；
y 出队，无事发生，此时最短路集合S = z, s, t, x, y；

$d$ 值表：

s	t	x	y	$S$
∞	∞	∞	∞	$\emptyset$
3	∞	7	∞	${z}$
3	6	7	8	${z, s}$
3	6	7	8	${z, s, t}$
3	6	7	8	${z, s, t, x}$
3	6	7	8	${z, s, t, x, y}$

$π$ 值表：

s	t	x	y	z
NIL	NIL	NIL	NIL	NIL
z	NIL	z	NIL	NIL
z	s	z	s	NIL
z	s	z	s	NIL
z	s	z	s	NIL
z	s	z	s	NIL

最大流#

本部分对应分篇：【算法设计与分析】最大流

Edmonds-Karp 算法采用 BFS 的方式去寻找图中分配的最大流，它每次都会选择 最短的增广路径（边数最少的路径）。它的过程非常简单，可以描述为：

画出残存网络（刚开始就是原图）。并令初始的流为 0。
BFS 扫描：找 $s$ 到 $t$ 边数最少的路。如果有两条路边数一样少，随便选一条（根据题目描述，通常选字典序小的，比如先走 $u$ 后走 $v$ ）。
增广：找出瓶颈，更新流量，更新残存图（加反向边）。
重复：再次 BFS。你会发现，随着残存图里正向边被切断，新的路径往往会通过反向边绕一下，或者走更远的边，路径长度逐渐增加。
直到 $s$ 和 $t$ 不连通。

接下来是一个例子：

给出一个流网络，使用 Edmonds-Karp 算法找到其最小割和最大流。在考虑邻结点顺序时遵循： ${s, v 1, v 2, v 3, v 4, t}$ .

对于这样的题目，我们首先将其转换为残存网络 $G_{f}$ ，如图 (b)。(图中阴影与本题无关)

忽略当前图中的流，从 0 开始。接下来开始进行 BFS，按照给出的邻结点顺序遍历。（注：下面过程中的图中，左侧图为当前步骤 执行前 的残存图 $G_{f}$ ，右侧图为当前步骤 执行后 的流网络图 $G$ 。）

(a). 第一次增广，先遍历 $v_{1}$ ，将选择： $s \to v_{1} \to v_{3} \to t$ 。它的瓶颈值 (minimum capacity) 是 $min (16, 12, 20) = 12$ ，所以更新该增广路径的流为 12，并更新残存图 (显示在 (b) 中的左图)。

(b). 第二次增广，残存图中先经过 $v_{1}$ 的路径以及没有了，继续遍历 $v_{2}$ ，将选择： $s \to v_{2} \to v_{4} \to t$ 。它的瓶颈值是 $min (13, 14, 4) = 4$ ，所以更新该增广路径的流为 4.

(c). 第三次增广，继续遍历 $v_{2}$ ，将选择： $s \to v_{2} \to v_{4} \to v_{3} \to t$ 。它的瓶颈值是 $min (13, 14, 7, 20) = 7$ ，所以更新该增广路径的流为 7。此前已有流的边将增加 7 的值。

(d). 第四次增广，先经过 $v_{2}$ 到 $t$ 的路已经全部断开，继续尝试遍历其他结点。发现无法找到任何增广路径，此时算法结束，最后的残存图如下：

至此，Edmonds-Karp 算法的流程就结束了，当前 (d) 的结果就是最小割和最大流的情况。我们可以通过残存图构造这样的最小割：

$S$ : 包含所有 $s$ 能到达的结点，即 $S = {s, v_{1}, v_{2}, v_{4}}$ .
$T$ : 包含所有 $s$ 无法到达的结点，即 $T = {v_{3}, t}$ .

最大流的值为 $∣ f ∣ = c (S, T) = c (v_{1}, v_{3}) + c (v_{4}, t) + c (v_{4}, v_{3}) = 12 + 4 + 7 = 23$

散列表——开放定址法（双散列）#

本部分对应分篇：【算法设计与分析】散列表

我们一般使用双散列比较多，下面是一个使用双散列的例子：

Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m = 11 using open addressing.

Illustrate the result of inserting these keys using double hashing with h1(k) = k mod m and h2(k) = 1 + (k mod (m - 1)).

我们整合一下上面的两个函数，可以得到函数h(k,i)，k表示关键字， i从0开始 ，表示初始位置的基础上进行偏移的度：

h(k, i) = (h₁(k) + i*h₂(k)) mod m = (k mod m + i(1 + (k mod (m - 1)))) mod m

我们的操作如下：

对于键值对10：h1(10) = 10 mod 11 = 1，插入键值对10到哈希表的第10个位置。
接下来是键值对22：h1(22) = 22 mod 11 = 0，插入键值对22到哈希表的第0个位置。
现在是键值对31：h1(31) = 31 mod 11 = 9，插入键值对31到哈希表的第9个位置。
接下来是键值对4：h1(4) = 4 mod 11 = 4，插入键值对4到哈希表的第4个位置。
现在是键值对15：h1(15) = 15 mod 11 = 4，4这个位置冲突了，继续计算h2(15) = 1 + (15 mod (11 - 1)) = 1 + 5 = 6，(4 + 6) mod 11= 10这个位置还是冲突，继续计算(4 + 2*6) mod 11 = 16 mod 11 = 5，插入键值对15到哈希表的第5个位置。
接下来是键值对28：h1(28) = 28 mod 11 = 6，插入键值对28到哈希表的第6个位置。
现在是键值对17：h1(17) = 17 mod 11 = 6，这个位置冲突了，计算h2(17) = 1 + (17 mod (11 - 1)) = 1 + 7 = 8，(6 + 8) mod 11 = 3，插入键值对17到哈希表的第3个位置。
接下来是键值对88：h1(88) = 88 mod 11 = 0，位置冲突继续计算，h2(88) = 1 + (88 mod (11 - 1)) = 1 + 8 = 9，(0+9) mod 11 = 9冲突，继续计算(0+2*9) mod 11 = 7，插入键值对88到哈希表的第7个位置。
最后是键值对59：h1(59) = 59 mod 11 = 4，位置冲突继续计算，h2(59) = 1 + (59 mod (11 - 1)) = 1 + 9 = 10，(4+10) mod 11 = 3冲突，(4+2*10) mod 11 = 2，插入键值对59到哈希表的第2个位置。

最后可以得到如下表格：

0	1	2	3	4	5	6	7	8	9	10
22		59	17	4	15	28	88		31	10

贪心算法——哈夫曼编码#

本部分对应分篇：【算法设计与分析】贪心算法

哈夫曼编码的贪心设计就非常明显了，只需要使用优先队列去存，每次都选择最小的两个合并，直到全部插入树中即可，例如：

以下字符频率基于斐波那契数列前8个数字的字符集的哈夫曼编码是怎样的? a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21

下面使用z(a,b)表示频数为z的节点左边的是频数a或字符a，右边的是频数b或字符b。

把它们按照频数加入优先队列Q中，顺序刚好为： a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21
取出前两个，合并插入到优先队列中得到： c:2 2(a,b) d:3 e:5 f:8 g:13 h:21
依次类推继续合并插入得： d:3 4( c,2(a,b) ) e:5 f:8 g:13 h:21
e:5 7( d,4( c,2(a,b) ) ) f:8 g:13 h:21
f:8 12( e, 7( d,4( c,2(a,b) ) ) ) g:13 h:21
g:13 20( f,12( e, 7( d,4( c,2(a,b) ) ) ) ) h:21
h:21 33( g,20( f,12( e, 7( d,4( c,2(a,b) ) ) ) )
54( h,33( g,20( f,12( e, 7( d,4( c,2(a,b) ) ) ) ) )

最终得到这样的一棵树，图(a)为该题答案，图(b)为前n为推广：

堆排序#

本部分对应分篇：【算法设计与分析】堆排序

这一节又分为分析和代码部分，其中比较重要的是如何维护堆和建堆。下面的证明可能与之前原文有所不同，选择好理解的就行。

分析#

证明左子树最大规模为2n/3#

由于堆是对应一棵完全二叉树，设它有n个结点根结点。 根的左子树结点数≥根结点的右子树结点数 。

对于一个完全二叉树，它的最后一层可能不是完全填满的。为了估计最大规模，假设我们假设左子堆是一个高度为 h 的满二叉树，右子堆是一个高度为 h-1 的满二叉树。

那么左子树的结点数 nl = ∑i∈[0,h] 2^i = 2^(h+1) - 1 ；右子树的结点数 nr = ∑i∈[0,h-1] 2^i = 2^h - 1

总结点数 n = nl + nr + 1 = 2^(h+1) - 1 + 2^h - 1 + 1 = 3*2^h - 1

于是 左子树结点数/总结点数 = 2^(h+1) - 1 / 3*2^h - 1 = 2*2^h - 1 / 3*2^h - 1 < 2*2^h / 3*2^h = 2/3 故左子树最大规模为2n/3。

分析维护堆#

维护堆是一个向下调整（Percolate Down）的过程，如果为大根堆，则判断当前根结点是否满足大于它的左右结点，如不满足，则替换为左右结点中最大的，接着递归以被替换位置为根向下调整。

它的伪代码为：

1
MAX-HEAPIFY(A, i)
2
    l = LEFT(i)
3
    r = RIGHT(i)
4
    if l ≤ A.heap-size and A[l] > A[i]
5
        largest = l
6
    else largest = i
7
    if r ≤ A.heap-size and A[r] > A[largest]
8
        largest = r
9
    if largest ≠ i
10
        exchange A[i] with A[largest]
11
        MAX-HEAPIFY(A, largest)

分析它非常简单，我们之前已经知道了子树最大规模为2n/3，故递归式为： T(n) = T(2n/3) + Θ(1) ；

根据Master Theorem Case 2， $n^{l o g_{2/3} 1} = 1 \in Θ (1)$ ，故 $T (n) = Θ (l g n)$

证明：对一个大小为n的堆，MAX-HEAPIFY的最坏情况运行时间为Ω(lgn)#

MAX-HEAPIFY的最坏情况下（是一个小根堆），每个根都需要运行一次MAX-HEAPIFY，此时一条路径上最长的为 $h = ⌊ l g n ⌋$ ，故最坏的运行时间为 $Ω (l g n)$ 。

证明叶结点下标#

证明: 当用数组表示存储n个元素的堆时，叶结点的下标分别为 $⌊ n /2 ⌋ + 1, ⌊ n /2 ⌋ + 2, \dots, n$ 。

这个很容易证明，我们想最后一个结点为n，它的父母结点p为 $⌊ n /2 ⌋$ 。此时有三种情况：

当父母结点p的左孩子为n的时候，且p不在这一层的末尾，那么p+1开始的结点到n都是叶子节点。 例如下图的堆：最后一位结点n的下标为8，值为1，它的父母结点的下标为 $⌊ n /2 ⌋ = 4$ ，那么从 $⌊ n /2 ⌋ + 1$ 到n的结点(4, 3, 2, 1)它们都是叶子节点。

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2
6
  /
7
 1

当父母结点p的右孩子为n的时候，且p不在这一层的末尾，那么p+1开始的结点到n都是叶子节点。 同理为右结点时，p的下一位一定也是叶子结点。例如：最后一位结点n的下标为9，值为2，它的父母结点的下标为 $⌊ n /2 ⌋ = 4$ ，那么从 $⌊ n /2 ⌋ + 1$ 到n的结点(4, 3, 2, 1, 2)它们都是叶子节点。

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2
6
  / \
7
 1   2

当父母结点p的右孩子为n的时候，且p在这一层的末尾，那么p+1开始的结点到n都是叶子节点。 此时这种情况下像之前所知的无论最后一位是左右都无所谓，父母结点的下一个就在最后一位的这一层，它们都是叶子结点。例如：最后一位结点n的下标为7，值为2，它的父母结点的下标为 $⌊ n /2 ⌋ = 3$ ，那么从 $⌊ n /2 ⌋ + 1$ 到n的结点(5, 4, 3, 2)它们都在最后一层，是叶子节点。

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2

上述为理解证明，但实际上证明可以使用反证法来证明：

假设 $⌊ n /2 ⌋ + 1$ 不位于最后一层，那么它一定有左孩子，其左孩子结点下标小于等于n。

我们证明它的左孩子： $LEFT (⌊ n /2 ⌋ + 1) = 2 (⌊ n /2 ⌋ + 1)$ 因为 $(n /2 - 1) \leq ⌊ n /2 ⌋ \leq n /2$ ，那么 $2 (⌊ n /2 ⌋ + 1) \geq 2 (n /2 - 1 + 1) = n$ ，此时它的左孩子一定大于等于n，假设不成立得证。

证明在高h的层上至多的结点数#

首先，我们先回顾：从根到节点的简单路径的长度是树中节点的深度。树的高度是从节点到叶子的最长下行路径上的边数，树的高度是它的根的高度。这意味着，高度从下往上依次是0~~H，而深度则是从上往下依次是0~~H。

有了上一个证明，我们知道 n元堆的叶结点的下标分别为 $⌊ n /2 ⌋ + 1, ⌊ n /2 ⌋ + 2, \dots, n$ 。

那么叶子结点的总数有： $n - (⌊ n /2 ⌋ + 1) + 1 \geq ⌈ n - n /2 ⌉ = ⌈ n /2 ⌉$

设高度为h的层有 $n_{h}$ 个结点，那么高度为0的层，它至多有 $⌈ n /2 ⌉$ 个叶子结点，因为当叶子结点全都在最后一层时成立。

那么使用数学归纳法：在高度为h的层有 $n_{h}$ 个结点， $n_{h} \leq ⌈ n / 2^{h + 1} ⌉$ ，

则在高度为h+1的层的结点数为 $n_{h + 1} \leq ⌈ n_{h} /2 ⌉ = ⌈ n / 2^{h + 1} /2 ⌉ = ⌈ n / 2^{h + 1} /2 ⌉ = ⌈ n / 2^{h + 1 + 1} ⌉$ 得证。

故 在高h的层上至多的结点数为 $⌈ n / 2^{h + 1} ⌉$ 。

建堆分析#

我们知道对于一颗完全二叉树， 根的左子树结点数≥根结点的右子树结点数 。那么当它满的时候，这棵树的高度为 $⌊ l g n ⌋$ 。

下面是建堆的代码：

1
BUILD-MAX-HEAP(A, n)
2
    A.heap-size = n
3
    for i = floor(n/2) down to 1
4
        MAX-HEAPIFY(A, i)

这个算法是从最后一个结点的父母结点开始，不断向上调整的过程。在每个 MAX-HEAPIFY(A, i) 中，它的时间复杂度看作是节点i到叶子节点的路径长度，这个路径长度等于这个节点的高度。因此，对于一个高度为h的节点，它的时间复杂度为O(h)。

在一个高度为 $H = ⌊ l g n ⌋$ 的完全二叉树中，高度为h的节点有 $2^{H - h} = 2^{⌊ l g n ⌋ - h} = 2^{⌊ l g n ⌋} / 2^{h}$ 个。根据之前的证明可以得到 $2^{⌊ l g n ⌋} / 2^{h} \leq ⌈ n / 2^{h + 1} ⌉$

设c为渐近符号中隐含的常数，故整个的时间复杂度为：

h = 0 \sum H - 1 2^{H - h} \times O (h) \times c \leq h = 0 \sum H - 1 ⌈ n / 2^{h + 1} ⌉ \times h \times c = c n h = 0 \sum ⌊ l g n ⌋ - 1 h / 2^{h + 1} \leq c n h = 0 \sum \infty h / 2^{h + 1}

$When 0 < x < 1$ , $\sum_{n = 0}^{\infty} x^{n} = 1/ (1 - x)$ 。

对这个公式两边同时求导(对x)，得到 $\sum_{n = 0}^{\infty} n \times x^{n - 1} = 1/ (1 - x)^{2}$ ，我们带入 $x = 1/2$ ，得到 $\sum_{n = 0}^{\infty} n \times (1/2)^{n - 1} = 1/ (1 - 1/2)^{2} = 4$ 。

将两边同时乘以 $(1/2)^{2}$ ，得到 $\sum_{n = 0}^{\infty} n \times (1/2)^{n + 1} = 1$ 。

回到原题中，这里的 $\sum_{h = 0}^{\infty} h / 2^{h + 1} = h \times (1/2)^{h + 1} = 1$ . 故有：

c n h = 0 \sum \infty h / 2^{h + 1} = c n \times 1 = c n = O (n)

于是乎建堆的过程，时间复杂度为 $O (n)$ 。

分析堆排序#

1
HEAPSORT(A, n)
2
    BUILD-MAX-HEAP(A, n)
3
    for i = n downto 2
4
        swap(A[1], A[i])
5
        A.heap-size = A.heap-size - 1
6
        MAX-HEAPIFY(A, 1)

对于堆排序，它的过程就非常简单了，因为有n-1次循环，每次MAX-HEAPIFY(A, 1)的时间复杂度为 $O (l g n)$ ，堆排序的时间复杂度为 $O (n l g n)$

代码#

编写MIN-HEAPIFY(A,i)#

维护堆是一个向下调整（Percolate Down）的过程，根据大根堆的思路，很容易知道小根堆的思路为找到i结点的左右结点，判断i结点是否为最小的，不是则替换，并递归被替换的位置。

于是它的伪代码：

1
MIN-HEAPIFY(A, i)
2
    l = LEFT(i)
3
    r = RIGHT(i)
4
    if l ≤ A.heap-size and A[l] < A[i]
5
        smallest = l
6
    else smallest = i
7
    if r ≤ A.heap-size and A[r] < A[smallest]
8
        smallest = r
9
    if smallest != i
10
        exchange A[i] with A[smallest]
11
        MIN-HEAPIFY(A, smallest)

使用循环重写MAX-HEAPIFY#

我们可以用循环来替换递归来提高效率。当最后的 largest == i 时，我们结束循环。于是就有：

1
MAX-HEAPIFY(A, i)
2
    while true
3
        l = LEFT(i)
4
        r = RIGHT(i)
5
        if l ≤ A.heap-size and A[l] > A[i]
6
            largest = l
7
        else largest = i
8
        if r ≤ A.heap-size and A[r] > A[largest]
9
            largest = r
10
        if largest == i
11
            return
12
        exchange A[i] with A[largest]
13
        i = largest

线性时间排序#

本篇原文：

https://hoyue.fun/algorithm_5.html

分析#

证明比较排序的下界#

对于一棵每个排列都是一个可达的叶结点的决策树来说，树的高度完全可以被确定。考虑一棵高度为h的决策树，它对应一个对n个元素所做的比较排序。

对于n个变量的问题，这n个变量有n!种可能的顺序，它在决策树中就有n!个叶结点。根据图中情况可以知道，若为满二叉树，在h层有 $2^{h}$ 个叶子结点，明显 $n! \leq 2^{h}$ 。

两边取对数得： h >= lg(n!)

根据Sterling 近似公式，有 n! ≈ √(2πn)(n/e)^n => n! > (n/e)^n 带入可得， h ≥ lg(n/e)^n = n lg(n/e) = n lg n - n lg e = Ω(n lg n)

分析桶排序#

桶排序的步骤为：

根据A数组新建B链表数组，并初始化为0。
将A数组中的元素依次按照一定的规则插入到桶中。（有点像散列表）。
对每个桶内部进行插入排序，当插入排序规模很小的时候，趋向于 $Θ (n)$ 。
按顺序输出每个桶（桶设置时是有序的）。

它的伪代码：

1
BUCKET-SORT(A, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        insert A[i] into list B[⌊n · A[i]⌋]
7
    for i = 0 to n - 1
8
        sort list B[i] with insertion sort
9
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
10
    return the concatenated lists

在最坏的情况下(所有的数据都插到同一个桶中)，我们发现除了插入排序外，其他的均为 $Θ (n)$ 。因为插入排序的时间代价为平方阶的，那么整体的桶排序时间代价为： $T (n) = Θ (n) + \sum_{(0, n - 1)} O (n^{2})$

我们计算平均的运行时间，对这个式子取数学期望(mean)：

$E (T (n)) = Θ (n) + E (\sum_{(0, n - 1)} O (n_{i}^{2}))$ $= Θ (n) + \sum_{(0, n - 1)} O (E (n_{i}^{2}))$

一共有n个桶，这个数据落入这个桶的概率为1/n，数据落入桶这个过程它满足二项分布 $n_{i} \sim B (n, 1/ n)$

$E (T (n)) = Θ (n) + \sum_{(0, n - 1)} O (E (n_{i}^{2}))$ $= Θ (n) + \sum_{(0, n - 1)} O (2 - 1/ n)$ $= Θ (n) + O (n)$ $= Θ (n)$

因为在二项分布中：

$E (x) = n p = 1;$
$Va r (x) = n p (1 - p) = 1 - 1/ n;$
$E (x^{2}) = Va r (x) + E^{2} (x) = n p (1 - p) + (n p)^{2} = 1 - 1/ n + 1 = 2 - 1/ n;$

故平均情况下为 $Θ (n)$ 但最坏的情况为 $Θ (n^{2})$ ，因为插入排序最差情况为 $Θ (n^{2})$

代码#

修改计数排序#

设由n个元素组成的输入序列每个元素都是区间[0: k]内的一个整数，且这些元素没有卫星数据，修改COUNTING-SORT，只用数组 A和C，将输出序列放在A中。

这样输入序列所有元素只能从 C 中复制，修改后COUNTING-SORT的伪代码如下：

1
COUNTING-SORT(A, n, k)
2
    let C[0:k] be new arrays
3
    for i = 0 to k
4
        C[i] = 0
5
    for j = 1 to n
6
        C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i.
7
    p = 1
8
    for i = 0 to k
9
        while C[i] > 0
10
            A[p] = i
11
            p = p + 1
12
            C[i] = C[i] - 1

基于CDF的桶排序#

设X为一个随机变量，设它的累计分布函数(CDF)为F(x) = P(X≤x)，设 $X_{1}, X_{2}, \dots, X_{n}$ 服从F(x)，且在 $O (1)$ 时间内可以计算得到(若给定 y 和 F(x)=y，能够在 $O (1)$ 时间内计算出x )，设计一个算法，能在平均情况为线性时间内完成排序。

这样的算法我们可以使用桶排序，设置F(x) = i/n，有n个桶，它们就满足二项分布了，这个就和桶排序基本一致，于是我们的伪代码可以写为：

1
BUCKET-SORT(X, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        if x_{i-1} ≤ X_i and X_i < x_i
7
        insert X_i into list B[i-1]
8
    for i = 0 to n - 1
9
        sort list B[i] with insertion sort
10
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
11
    return the concatenated lists

其中， $x_{i}$ 是满足 $F (x_{i}) = i / n$ 的值，可以在 $O (1)$ 时间内计算得到。由于输入数据服从分布F(x)，每个桶期望包含的元素数量为1，因此平均情况下算法的时间复杂度为 $Θ (n)$ 。

后记#

通过这次期末复习专题，我们系统回顾了算法设计与分析的核心内容，包括散列表的开放定址法、动态规划的最优二叉搜索树、贪心算法的哈夫曼编码、基本图论的 BFS 和 DFS、单源最短路的 Bellman-Ford 和 Dijkstra 算法、最大流中的 Edmonds-Karp 算法、堆排序以及线性时间排序算法。

这些算法各有特点和适用场景：

散列表 通过双散列等开放定址法有效解决冲突问题
动态规划 通过最优子结构和重叠子问题性质求解最优化问题
贪心算法 在每步做出局部最优选择，在特定问题上能得到全局最优解
图论算法 为后续复杂图算法奠定基础
最短路算法 分别适用于有负权边和无负权边的情况
堆排序 保证 $O (n l g n)$ 的时间复杂度
线性时间排序 在特定条件下突破比较排序的下界

掌握这些基础算法的原理、实现和分析方法，对于解决实际问题和进一步学习高级算法具有重要意义。算法设计与分析不仅是计算机科学的核心课程，更是培养逻辑思维和问题求解能力的重要途径。