2026-06-23

课程笔记

高级算法期末复习总整理：12 个考点一篇过

这篇文章整理了高级算法期末复习的 12 个核心考点，覆盖复杂度分析、渐进记号、递推关系、主定理、堆、快速排序平均分析、对抗策略、线性选择、平摊分析、图搜索、贪心和动态规划。

01. 算法的最坏复杂度、平均复杂度和最优性
02. 大 O、大 Ω、大 Θ 的定义和相关函数证明
03. 递归关系求解
04. 平滑函数性质和主定理应用
05. 堆的定义、数组表示和堆操作
06. 复用快排平均复杂度分析方法处理其他问题
07. 对抗策略及经典选择问题下界
08. 线性时间选择算法的实现和应用
09. 平摊分析、MultiPop Stack、DeleteLargerHalf 和栈模拟队列
10. 深度优先、广度优先和图上搜索问题
11. 贪心法的思想和特点、换硬币和单源最短路径
12. 动态规划的思想和经典问题

01. 算法的最坏复杂度、平均复杂度和最优性

复习资料

01-Introduction.pptx 第 20 页：最坏复杂度；第 24-26 页：平均复杂度；第 27-30 页：最优性、上下界
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：最坏复杂度

最坏复杂度是在所有可能输入中，运行时间最长的情况。

要会说明：

输入规模为 $n$ 。
不同输入实例可能导致不同运行时间。
最坏复杂度取所有实例中的最大运行时间。

例子：在含有 $n$ 个元素的数组中顺序查找某个元素，最坏情况是元素在最后一个位置，或元素不存在，需要比较 $n$ 次。

考点2：平均复杂度

平均复杂度是按输入分布对运行代价求期望。若题目没有给概率分布，通常按均匀分布理解。

顺序查找成功时，如果目标等概率出现在 $1$ 到 $n$ 的任意位置，平均比较次数为：

\frac{1 + 2 + \dots + n}{n} = \frac{n + 1}{2}

如果查找失败，则需要比较 $n$ 次。

考点3：最优性

证明算法最优通常分两步：

证明任何算法完成该任务都至少需要某个下界。
证明当前算法正好达到该下界。

也就是：

下界 \leq 任意算法代价

当前算法代价 = 下界

所以当前算法最优。

例子：从 n 个数中找最大值

顺序扫描算法：

先假设第一个元素为当前最大值。
依次与后续元素比较。
如果发现更大的值，则更新最大值。
一共比较 $n - 1$ 次。

最优性证明：

要确认某个元素是最大值，其他 $n - 1$ 个元素都必须至少输过一次。
每次比较最多只能产生一份“输”的信息。
因此任何算法至少需要 $n - 1$ 次比较。
顺序扫描算法正好用 $n - 1$ 次，因此最优。

02. 大 O、大 Ω、大 Θ 的定义和相关函数证明

复习资料

02-Asymptotics.ppt 第 4-15 页：渐进增长率、大 O / 大 Ω / 大 Θ 定义和性质
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：什么是大O、大Ω、大Θ

$O$ 表示上界：

f (n) = O (g (n))

含义：存在正常数 $c$ 和 $n_{0}$ ，当 $n \geq n_{0}$ 时：

0 \leq f (n) \leq c g (n)

$Ω$ 表示下界：

f (n) = Ω (g (n))

含义：存在正常数 $c$ 和 $n_{0}$ ，当 $n \geq n_{0}$ 时：

0 \leq c g (n) \leq f (n)

$Θ$ 表示同阶：

f (n) = Θ (g (n))

含义：同时有 $f (n) = O (g (n))$ 和 $f (n) = Ω (g (n))$ 。

考点2：大O、大Ω、大Θ的性质

根据 02-Asymptotics.ppt 第 14、15 页，重点记下面几类性质。

传递性

如果两个函数之间的渐进关系可以一级一级传下去，那么可以直接合并中间函数。

f = O (g), g = O (h) \Rightarrow f = O (h)

f = Ω (g), g = Ω (h) \Rightarrow f = Ω (h)

f = Θ (g), g = Θ (h) \Rightarrow f = Θ (h)

对偶与对称性质

$O$ 和 $Ω$ 是互相反向的关系：

f = O (g) ⟺ g = Ω (f)

$Θ$ 是真正的同阶关系，因此左右可以交换：

f = Θ (g) ⟺ g = Θ (f)

和式性质

两个复杂度类相加时，整体由增长更快的一项主导：

O (f) + O (g) = O (max (f, g))

如果 $g = O (f)$ ，也就是 $g$ 不比 $f$ 增长更快，那么：

O (f) + O (g) = O (f)

这就是“低阶项可以忽略”的来源。

常数因子可忽略

若 $C$ 是正常数，则：

O (C f (n)) = O (f (n))

也就是说，渐进分析中常数倍不影响复杂度阶。

自反性

任意函数都属于自身的上界类：

f \in O (f)

考点3：常见增长阶

从慢到快：

lo g n < n^{a} < b^{n} < n! < n^{n}

其中 $a > 0$ ， $b > 1$ 。

要会比较：

$lo g n$ 和 $n^{k}$
$n^{k}$ 和 $a^{n}$
$n!$ 和 $a^{n}$
多项式项相加时谁主导

03. 递归关系求解

复习资料

03-Recursion.ppt 第 12-16 页：形似斐波那契数列的二阶线性齐次递推、特征方程和显式公式
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：解二阶线性齐次递推

重点形式：

a_{n} = r_{1} a_{n - 1} + r_{2} a_{n - 2}

复习 PDF 和录音中强调：主要考二阶，且只考两个根不相等的情况。

特征方程

特征方程是把递推关系转成普通代数方程的一种方法。它的核心想法是：先猜这个递推式的解可能长得像一个指数函数：

a_{n} = x^{n}

把它代入递推式：

x^{n} = r_{1} x^{n - 1} + r_{2} x^{n - 2}

两边同时除以 $x^{n - 2}$ ，得到：

x^{2} = r_{1} x + r_{2}

整理后就是特征方程：

x^{2} - r_{1} x - r_{2} = 0

求根时使用二次方程公式。对于一般二次方程：

a x^{2} + b x + c = 0

两个根为：

x = \frac{- b \pm b ^{2} - 4 a c}{2 a}

对应到这里：

a = 1, b = - r_{1}, c = - r_{2}

所以：

x = \frac{r _{1} \pm r _{1}^{2} + 4 r _{2}}{2}

也就是说，特征方程的根就是“哪些指数底数 $x$ 可以满足这个递推式”。如果这个方程有两个不同的根 $s_{1}$ 和 $s_{2}$ ，那么 $s_{1}^{n}$ 和 $s_{2}^{n}$ 都是这个递推式的基础解。

二阶线性齐次递推的通解就是这两个基础解的线性组合：

a_{n} = u s_{1}^{n} + v s_{2}^{n}

其中 $u$ 、 $v$ 是两个待定常数，需要用初始条件求出，例如代入 $a_{0}$ 、 $a_{1}$ 。

解题步骤

从递推式写出特征方程。
解二次方程，得到两个根 $s_{1}$ 、 $s_{2}$ 。
写出通解：

a_{n} = u s_{1}^{n} + v s_{2}^{n}

代入初始条件，解出 $u$ 和 $v$ 。
写出最终通项。

斐波那契型例子

F_{n} = F_{n - 1} + F_{n - 2}

对应：

r_{1} = 1, r_{2} = 1

x^{2} - x - 1 = 0

两个根：

s_{1} = \frac{1 + 5}{2}

s_{2} = \frac{1 - 5}{2}

所以：

F_{n} = u s_{1}^{n} + v s_{2}^{n}

采用常见初值 $F_{0} = 0$ 、 $F_{1} = 1$ ，代入通解：

F_{0} = u + v = 0

F_{1} = u s_{1} + v s_{2} = 1

由 $u + v = 0$ 得到 $v = - u$ ，代入第二个式子：

u (s_{1} - s_{2}) = 1

因为：

s_{1} - s_{2} = 5

所以：

u = \frac{1}{5}, v = - \frac{1}{5}

最终结果为：

F_{n} = \frac{1}{5} s_{1}^{n} - \frac{1}{5} s_{2}^{n}

也就是：

F_{n} = \frac{1}{5} (\frac{1 + 5}{2})^{n} - \frac{1}{5} (\frac{1 - 5}{2})^{n}

04. 平滑函数性质和主定理应用

复习资料

03-Recursion.ppt 第 9 页：平滑函数性质
03-Recursion.ppt 第 27-30 页：应用主定理求解一般式
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：平滑函数性质

定义

根据 03-Recursion.ppt 第 9 页，设 $f (n)$ 是定义在自然数集合上的非负、最终非降函数。如果满足：

f (2 n) \in Θ (f (n))

则称 $f (n)$ 是平滑函数。

直观理解：当输入规模从 $n$ 变成 $2 n$ 时，函数值只改变一个常数倍量级，不会发生指数级跳变。

作用

平滑函数性质主要用于处理递归式中的向上取整、向下取整，使它们不会影响最终渐进复杂度。

应理解：

分治递归中常出现 $T (⌊ n / c ⌋)$ 或 $T (⌈ n / c ⌉)$ 。
在满足一定平滑性条件时，可按 $T (n / c)$ 来分析渐进阶。
考试重点通常不是死背定义，而是知道它为什么能帮助主定理应用。

典型平滑函数

课件中给出的平滑函数包括：

lo g n, n, n lo g n, n^{α} (α \geq 0)

例如：

2 n lo g (2 n) = 2 n (lo g n + lo g 2) \in Θ (n lo g n)

所以 $n lo g n$ 是平滑函数。

典型非平滑函数

非平滑函数的关键特征是：从 $n$ 变成 $2 n$ 后，函数值不是只差一个常数倍，而是会跨越不同增长量级。

例子 1：指数函数。

f (n) = 2^{n}

则：

f (2 n) = 2^{2 n}

比较二者：

\frac{f ( 2 n )}{f ( n )} = \frac{2 ^{2 n}}{2 ^{n}} = 2^{n}

这个比值会随着 $n$ 增大而无限增大，不是常数倍。因此：

2^{2 n} \in / Θ (2^{n})

所以 $2^{n}$ 不是平滑函数。

例子 2：阶乘函数。

f (n) = n!

则：

f (2 n) = (2 n)!

比较二者：

\frac{f ( 2 n )}{f ( n )} = \frac{( 2 n )!}{n !} = (n + 1) (n + 2) \dots (2 n)

这个乘积会快速增大，不可能被常数限制住。因此：

(2 n)! \in / Θ (n!)

所以 $n!$ 不是平滑函数。

例子 3：带剧烈振荡的分段函数。

f (n) = {n, n = 2^{2 k} n^{2}, n = 2^{2 k + 1}

当 $n = 2^{2 k}$ 时：

f (n) = n

但：

2 n = 2^{2 k + 1}

所以：

f (2 n) = (2 n)^{2} = 4 n^{2}

于是：

\frac{f ( 2 n )}{f ( n )} = \frac{4 n ^{2}}{n} = 4 n

这个比值也不是常数倍，因此这个函数不是平滑函数。

考点2：应用主定理求解一般式

分治递推的一般形式

根据 03-Recursion.ppt 第 27 页，分治递归的一般形式为：

T (n) = b T (n / c) + f (n)

其中：

$T (n)$ ：规模为 $n$ 的问题所需时间。
$b$ ：子问题个数。
$n / c$ ：每个子问题规模。
$f (n)$ ：根节点处划分、合并或其他非递归代价。

递推式的意思是：为了解一个规模为 $n$ 的问题，先递归解决 $b$ 个规模为 $n / c$ 的子问题，再额外花费 $f (n)$ 的时间做非递归处理。

子问题个数 $b$ 和子问题规模 $n / c$ 都由算法的分治方式决定。它们不是同一个东西，但通常有关联：

$b$ 越大，递归调用越多。
$c$ 越大，单个子问题越小。
每一层递归的子问题总规模可以粗略看成 $b \cdot (n / c)$ 。

例如归并排序把数组分成 $2$ 个规模为 $n /2$ 的子问题，所以 $b = 2$ 、 $c = 2$ ；二分查找只递归处理 $1$ 个规模为 $n /2$ 的子问题，所以 $b = 1$ 、 $c = 2$ 。

递归树深度与临界指数

设基本情形出现在深度 $D$ ，则：

\frac{n}{c ^{D}} = 1

所以：

D = \frac{lo g n}{lo g c}

叶子数为：

L = b^{D} = b^{\frac{l o g n}{l o g c}}

经过代数化简：

L = n^{E}

其中：

E = \frac{lo g b}{lo g c} = lo g_{c} b

$E$ 称为临界指数。主定理的核心就是比较：

f (n) 和 n^{E}

也就是比较根节点非递归代价和叶子层总代价的增长速度。

行和思想

根据 03-Recursion.ppt 第 28-29 页，递归树的解等于所有节点的非递归代价之和，也可以看成每一层行和之和。

第 $0$ 层行和是 $f (n)$ 。
第 $D$ 层行和是 $Θ (n^{E})$ 。
如果行和逐层增大，最后一层主导。
如果每层行和同阶，层数乘以单层代价。
如果行和逐层减小，第一层主导。

主定理三种情况

根据 03-Recursion.ppt 第 30 页：

情况 1：叶子层或子问题代价主导。

f (n) \in O (n^{E - ε}), ε > 0

则：

T (n) \in Θ (n^{E})

情况 2：每层代价均衡。

f (n) \in Θ (n^{E})

则：

T (n) \in Θ (f (n) lo g n)

因为此时每层贡献差不多，递归树深度是 $Θ (lo g n)$ 。

情况 3：根节点非递归代价主导。

f (n) \in Ω (n^{E + ε}), ε > 0

并且课件给出一个上界限制：

f (n) \in O (n^{E + δ}), δ \geq ε

则：

T (n) \in Θ (f (n))

课件强调：正的 $ε$ 很关键，它会导致三种情况之间存在间隙。

三种情况的例子

情况 1 例子：

T (n) = 8 T (n /2) + n^{2}

这里 $b = 8$ 、 $c = 2$ 、 $f (n) = n^{2}$ ，先算：

E = lo g_{2} 8 = 3

所以：

n^{E} = n^{3}

因为：

f (n) = n^{2} = O (n^{3 - 1})

所以属于情况 1：

T (n) = Θ (n^{3})

情况 2 例子：

T (n) = 2 T (n /2) + n

这里 $b = 2$ 、 $c = 2$ 、 $f (n) = n$ ，先算：

E = lo g_{2} 2 = 1

所以：

n^{E} = n

因为：

f (n) = Θ (n)

所以属于情况 2：

T (n) = Θ (n lo g n)

这就是归并排序的复杂度形式。

情况 3 例子：

T (n) = 4 T (n /2) + n^{3}

这里 $b = 4$ 、 $c = 2$ 、 $f (n) = n^{3}$ ，先算：

E = lo g_{2} 4 = 2

所以：

n^{E} = n^{2}

因为：

f (n) = n^{3} = Ω (n^{2 + 1})

所以属于情况 3：

T (n) = Θ (n^{3})

规整条件补充

有些教材在第三种情况中还会要求规整条件：

b f (n / c) \leq q f (n)

其中 $q < 1$ ，并且当 $n$ 足够大时成立。

它的直观含义是：下一层所有子问题的非递归代价加起来，必须比当前层非递归代价小一个固定比例。

对于：

T (n) = 4 T (n /2) + n^{3}

有：

4 f (n /2) = 4 (\frac{n}{2})^{3} = \frac{1}{2} n^{3}

因此可取 $q = 1/2$ ，满足规整条件。

不满足规整条件的例子：

T (n) = 2 T (n /2) + f (n)

其中：

f (n) = {n^{2}, n = 2^{2 k} n^{3}, n = 2^{2 k + 1}

这里 $b = 2$ 、 $c = 2$ ，所以 $E = 1$ 。由于 $f (n)$ 至少是 $n^{2}$ 量级，看起来像主定理第三种情况。

但取 $n = 2^{2 k}$ ，此时：

f (n) = n^{2}

而 $n /2 = 2^{2 k - 1}$ ，是奇数次幂，因此：

f (n /2) = (\frac{n}{2})^{3}

所以：

2 f (n /2) = 2 (\frac{n}{2})^{3} = \frac{n ^{3}}{4}

若要满足规整条件，就需要：

\frac{n ^{3}}{4} \leq q n^{2}

也就是：

\frac{n}{4} \leq q

当 $n$ 足够大时，不可能存在固定的 $q < 1$ 满足它。因此这个例子不满足规整条件，不能直接套用主定理第三种情况。

从题意翻译递推式

例子：一个规模为 $n$ 的问题，分成 $4$ 个规模为 $n /3$ 的子问题，合并代价为 $n^{2}$ 。

递推式：

T (n) = 4 T (n /3) + n^{2}

比较：

E = lo g_{3} 4

n^{E} = n^{l o g_{3} 4}

因为 $n^{2}$ 更大，通常进入主定理第三种情况，得到：

T (n) = Θ (n^{2})

05. 堆的定义、数组表示和堆操作

复习资料

06-HeapSort.ppt 第 5-15 页：堆的定义、堆排序策略、fixHeap、建堆、数组表示
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：堆的定义

堆结构

根据 06-HeapSort.ppt 第 5 页，二叉树 $T$ 是堆结构，需要满足：

$T$ 至少到深度 $h - 1$ 都是满的。
所有叶子都在深度 $h$ 或 $h - 1$ 。
深度为 $h$ 的叶子路径都位于深度为 $h - 1$ 的叶子路径左边。

直观理解：堆首先是一棵“尽量从上到下、从左到右填满”的二叉树，也就是通常所说的完全二叉树。

偏序树性质

课件讨论的是最大堆。若一棵树满足最大偏序树性质，则任意节点的关键字都大于或等于它每个子节点的关键字：

key (parent) \geq key (child)

因此最大堆的根节点一定保存整棵堆中的最大关键字：

root (H) = max (H)

堆的完整定义

堆等于：

堆结构 + 偏序树性质

也就是说，堆既要有接近完全二叉树的形状，又要满足父节点不小于子节点的顺序要求。

若是最小堆，则不等号方向相反：

key (parent) \leq key (child)

考点2：用数组表示堆

为什么可以用数组表示

堆结构接近完全二叉树，节点位置非常规整，所以不需要显式保存左右指针。只要把节点按层序从左到右放入数组，就可以通过下标快速找到父节点和子节点。

课件中的 1 下标表示

06-HeapSort.ppt 第 15 页使用从 $1$ 开始的数组下标。

对于数组元素 $E [i]$ ：

left (i) = 2 i

right (i) = 2 i + 1

parent (i) = ⌊ \frac{i}{2} ⌋

因此：

$E [1]$ 是堆顶。
$E [2 i]$ 是 $E [i]$ 的左孩子。
$E [2 i + 1]$ 是 $E [i]$ 的右孩子。
$E [⌊ i /2 ⌋]$ 是 $E [i]$ 的父节点。

0 下标补充

如果程序数组从 $0$ 开始，则公式改为：

left (i) = 2 i + 1

right (i) = 2 i + 2

parent (i) = ⌊ \frac{i - 1}{2} ⌋

考试或写伪代码时要先看清下标从 $0$ 开始还是从 $1$ 开始。

考点3：实现堆操作

堆排序策略

根据 06-HeapSort.ppt 第 7 页，堆排序的基本策略是：

由待排序元素集合 $E$ 构造堆 $H$ 。
每次取出堆顶最大元素。
删除堆顶后修复堆。
将取出的最大元素从数组末尾向前放。

伪代码思想为：

constructHeap (H) for i = n, n - 1, \dots, 1 : curMax = getMax (H) deleteMax (H) E [i] = curMax

`deleteMax`

最大堆中最大元素总在根节点。删除最大元素时，不能直接空出根节点，否则堆结构会被破坏。

课件第 7 页给出的思路是：

把最低层最右边的元素复制为 $K$ 。
删除最低层最右边的节点。
根节点位置变成空位。
调用 fixHeap(H,K)，把 $K$ 放到合适位置，同时恢复偏序树性质。

`fixHeap`

根据 06-HeapSort.ppt 第 8 页，fixHeap(H,K) 的输入条件是：

$H$ 是非空二叉树。
根节点位置暂时为空。
左子树和右子树已经满足偏序树性质。
有一个元素 $K$ 需要插入到堆中。

目标是把 $K$ 插入到合适位置，使整棵树重新满足最大堆性质。

基本过程：

如果 $H$ 是叶子节点，直接把 $K$ 放入根节点。
否则，在左右子树根节点中选出关键字较大的那个，记为 largerSubHeap。
如果 $K$ 的关键字大于等于 largerSubHeap 的根关键字，则把 $K$ 放入当前根节点。
否则，把 largerSubHeap 的根节点上移到当前根节点。
空位移动到 largerSubHeap 的根位置，继续递归执行 fixHeap(largerSubHeap,K)。

这个过程可以理解为：空位一路向下移动，每次让较大的孩子上移，直到 $K$ 能放在不破坏堆序的位置。

`fixHeap` 的复杂度

根据 06-HeapSort.ppt 第 10 页，fixHeap 每次递归最多做两次比较：

一次比较左右孩子，找出较大的子堆。
一次比较 $K$ 和较大孩子的根。

每次递归树高减少 $1$ ，因此最坏情况下比较次数不超过：

2 h

其中 $h$ 是堆的高度。由于堆是完全二叉树：

h = Θ (lo g n)

所以：

fixHeap (n) = O (lo g n)

建堆 `constructHeap`

根据 06-HeapSort.ppt 第 11-12 页，如果左右子树都已经满足偏序树性质，那么对当前根调用：

fixHeap (H, root (H))

就可以让当前子树也满足偏序树性质。

因此建堆可以采用后序遍历思想：

先递归处理左子树。
再递归处理右子树。
最后对根节点执行 fixHeap。

伪代码思想为：

constructHeap (H) : if H is not a leaf: constructHeap (left (H)) constructHeap (right (H)) K = root (H) fixHeap (H, K)

建堆复杂度

06-HeapSort.ppt 第 13 页说明：建堆总时间是线性的。

虽然单次 fixHeap 最坏是 $O (lo g n)$ ，但建堆时不是每个节点都会下滤整棵树高度：

靠近叶子的节点很多，但高度很小。
靠近根的节点高度大，但数量很少。

把所有节点的下滤代价加起来，总复杂度为：

constructHeap (n) = Θ (n)

堆排序总复杂度为：

constructHeap (n) + n \cdot O (lo g n) = O (n) + O (n lo g n) = O (n lo g n)

06. 复用快排平均复杂度分析方法处理其他问题

复习资料

04-Quicksort.ppt 第 28-35 页：快排平均比较次数递推式及其求解
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点：复用快排平均复杂分析方法

讲解例子：快排平均比较次数

随机划分模型

根据 04-Quicksort.ppt 第 28 页，快排选定分割元素 splitPoint 后，会把剩余元素分成两个子区间。

若输入规模为 $n$ ，splitPoint 的位置记为 $i$ ，则：

左子问题规模为 $i$ 。
右子问题规模为 $n - 1 - i$ 。
$i \in 0, 1, 2, \dots, n - 1$ 。
随机情况下，每个 $i$ 出现的概率都是 $\frac{1}{n}$ 。

第一轮为了找出 splitPoint 的位置，需要把它和其余 $n - 1$ 个元素比较，所以当前层比较次数是：

n - 1

平均比较次数递推式

设 $A (n)$ 表示快速排序处理 $n$ 个元素时的平均比较次数，并且：

A (0) = A (1) = 0

当分割点位置为 $i$ 时，递归子问题代价为：

A (i) + A (n - 1 - i)

对所有可能的 $i$ 取平均，得到：

A (n) = (n - 1) + \frac{1}{n} i = 0 \sum n - 1 (A (i) + A (n - 1 - i))

由于 $A (i)$ 和 $A (n - 1 - i)$ 只是同一组值正向、反向各出现一次，所以：

i = 0 \sum n - 1 (A (i) + A (n - 1 - i)) = 2 i = 0 \sum n - 1 A (i)

又因为 $A (0) = 0$ ，所以可化简为：

A (n) = (n - 1) + \frac{2}{n} i = 1 \sum n - 1 A (i)

也可以写成：

A (n) = \frac{n ( n - 1 ) + 2 \sum _{i = 1}^{n - 1} A ( i )}{n}

这里的理解是：

$n (n - 1)$ ： $n$ 种 pivot 情况下，本层划分比较次数的总和。
$2 \sum_{i = 1}^{n - 1} A (i)$ ： $n$ 种 pivot 情况下，左右子问题平均递归代价的总和。
最后除以 $n$ ：对 $n$ 种等概率情况取平均。

根据递推式推出复杂度

根据 04-Quicksort.ppt 第 34-35 页，可以直接从递推式推出平均复杂度。

已知：

A (n) = (n - 1) + \frac{2}{n} i = 1 \sum n - 1 A (i)

对应地：

A (n - 1) = (n - 2) + \frac{2}{n - 1} i = 1 \sum n - 2 A (i)

把第一个式子乘以 $n$ ，第二个式子乘以 $n - 1$ ，再相减：

n A (n) - (n - 1) A (n - 1)

= n (n - 1) + 2 i = 1 \sum n - 1 A (i) - (n - 1) (n - 2) - 2 i = 1 \sum n - 2 A (i)

中间的求和项大部分抵消，只剩下：

n A (n) - (n - 1) A (n - 1) = 2 A (n - 1) + 2 (n - 1)

所以：

n A (n) = (n + 1) A (n - 1) + 2 (n - 1)

两边除以 $n (n + 1)$ ：

\frac{A ( n )}{n + 1} = \frac{A ( n - 1 )}{n} + \frac{2 ( n - 1 )}{n ( n + 1 )}

令：

B (n) = \frac{A ( n )}{n + 1}

则：

B (n) = B (n - 1) + \frac{2 ( n - 1 )}{n ( n + 1 )}

又因为 $A (1) = 0$ ，所以 $B (1) = 0$ 。展开得到：

B (n) = i = 1 \sum n \frac{2 ( i - 1 )}{i ( i + 1 )}

利用：

\frac{1}{i ( i + 1 )} = \frac{1}{i} - \frac{1}{i + 1}

可以化为：

B (n) = 2 i = 1 \sum n \frac{1}{i} - \frac{4 n}{n + 1}

其中调和级数满足：

i = 1 \sum n \frac{1}{i} = O (lo g n)

因此：

B (n) = O (lo g n)

而：

A (n) = (n + 1) B (n)

所以：

A (n) = O (n lo g n)

更精确地说，快排的平均比较次数是 $Θ (n lo g n)$ 量级。PPT 第 35 页还给出近似形式：

A (n) \approx 1.386 n l g n - 2.846 n

本节要复用的不是“排序”这个动作，而是下面这个分析模式：

随机选 pivot + 线性划分 + 递归处理左右子问题 \Rightarrow O (n lo g n)

如果某个问题每一轮的具体比较次数不是 $n - 1$ ，而是 $2 n - 1$ ，则递推式变成：

X (n) = (2 n - 1) + \frac{2}{n} i = 1 \sum n - 1 X (i)

同样用第 34-35 页的方法，可得：

n X (n) = (n + 1) X (n - 1) + (4 n - 3)

令：

Y (n) = \frac{X ( n )}{n + 1}

则：

Y (n) = Y (n - 1) + \frac{4 n - 3}{n ( n + 1 )}

因为：

\frac{4 n - 3}{n ( n + 1 )} = O (\frac{1}{n})

所以：

Y (n) = O (i = 1 \sum n \frac{1}{i}) = O (lo g n)

从而：

X (n) = O (n lo g n)

可能考题1：螺丝螺母配对

问题描述

有 $n$ 个螺丝和 $n$ 个螺母，每个螺丝恰好匹配一个螺母。

限制条件是：

螺丝之间不能互相比较。
螺母之间不能互相比较。
只能拿一个螺丝和一个螺母比较，判断螺丝是偏大、偏小，还是刚好匹配。

目标是找出全部螺丝和螺母的匹配关系。

算法思想

这个问题可以复用快排划分思想：

随机选一个螺丝作为 pivot。
用这个螺丝和所有螺母比较，把螺母分成小于、匹配、大于三类。
找到与 pivot 螺丝匹配的螺母。
再用这个匹配螺母去划分所有螺丝，把螺丝也分成小于、匹配、大于三类。
左边螺丝只可能匹配左边螺母，右边螺丝只可能匹配右边螺母。
对左右两个子问题递归处理。

递推式和复杂度

螺丝螺母配对中：

pivot 是随机选出的螺丝。
一轮操作能把问题划分成左右两个子问题。
pivot 匹配项的位置等概率落在 $0, 1, \dots, n - 1$ 。

每一轮的具体比较次数是：

n + (n - 1) = 2 n - 1

其中：

用 pivot 螺丝比较全部 $n$ 个螺母，需要 $n$ 次比较。
找到匹配螺母后，用它比较剩下 $n - 1$ 个螺丝，需要 $n - 1$ 次比较。

如果 pivot 匹配项的位置为 $i$ ，则左子问题规模为 $i$ ，右子问题规模为 $n - 1 - i$ 。

设 $M (n)$ 表示平均比较次数，则：

M (n) = (2 n - 1) + \frac{1}{n} i = 0 \sum n - 1 (M (i) + M (n - 1 - i))

也就是：

M (n) = (2 n - 1) + \frac{2}{n} i = 1 \sum n - 1 M (i)

这个式子和快排平均比较次数递推式同型，只是本层代价从 $n - 1$ 变成 $2 n - 1$ 。根据前面的直接推导：

M (n) = O (n lo g n)

可能考题2：同学和衣服尺码匹配

问题描述

有 $n$ 个同学和 $n$ 件衣服，每个同学恰好有一件合适尺码的衣服。

在不知道具体尺码数字的情况下，允许做的比较是：让某个同学试某件衣服，判断衣服对这个同学来说：

偏小。
正好合适。
偏大。

目标是为每个同学匹配对应的衣服。

这个问题和螺丝螺母配对本质相同：

同学 \leftrightarrow 螺丝, 衣服 \leftrightarrow 螺母

算法思想

随机选一个同学作为 pivot。
让该同学试所有衣服，将衣服分成偏小、合适、偏大三类。
找到该同学对应的合适衣服。
用这件衣服去和所有同学比较，将同学分成需要更小衣服、正好匹配、需要更大衣服三类。
偏小衣服集合只可能匹配需要更小衣服的同学集合。
偏大衣服集合只可能匹配需要更大衣服的同学集合。
分别递归处理左右两个子问题。

递推式和复杂度

设 $C (n)$ 表示为 $n$ 个同学匹配 $n$ 件衣服的平均比较次数。

每一轮的具体比较次数是：

n + (n - 1) = 2 n - 1

其中：

pivot 同学试全部 $n$ 件衣服，需要 $n$ 次比较。
找到合适衣服后，用这件衣服比较剩下 $n - 1$ 个同学，需要 $n - 1$ 次比较。

pivot 同学对应衣服的相对位置等概率落在所有可能位置上。如果该位置为 $i$ ，则左子问题规模为 $i$ ，右子问题规模为 $n - 1 - i$ 。

所以平均递推式为：

C (n) = (2 n - 1) + \frac{1}{n} i = 0 \sum n - 1 (C (i) + C (n - 1 - i))

化简后：

C (n) = (2 n - 1) + \frac{2}{n} i = 1 \sum n - 1 C (i)

该递推式和螺丝螺母配对完全同型，因此：

C (n) = O (n lo g n)

所以，在只能跨集合比较、不能直接知道尺码数值的情况下，仍然可以用类似快排平均分析的方法，得到平均时间复杂度：

O (N lo g N)

07. 对抗策略及经典选择问题下界

复习资料

07-Selection.ppt 第 3-17 页：最大最小、对抗策略、第二大元素及下界
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：对抗策略的含义

选择问题背景

根据 07-Selection.ppt 第 4 页，选择问题是：

给定包含 $n$ 个关键字的集合 $E$ ，以及整数 $k$ ，满足：

1 \leq k \leq n

要求找出第 $k$ 小的元素。

找最大值和最小值是选择问题的特殊情况：

k = n \Rightarrow 找最大值

k = 1 \Rightarrow 找最小值

下界证明的基本想法

对抗策略用于证明比较类算法的下界。它不是先固定一个输入，而是假设有一个“对手”在算法比较两个元素时回答比较结果。

对手的目标是：

始终保持回答前后一致。
尽量让算法每次比较获得更少的新信息。
迫使算法做更多比较后，才能唯一确定答案。

因此，对抗策略常用于证明：

任何算法至少需要多少次比较

找最大值的下界

07-Selection.ppt 第 5 页给出找最大值的基本下界。

要确定某个元素 $x$ 是最大值，必须知道其他 $n - 1$ 个元素都不可能是最大值。一个元素只有在某次比较中输给别人后，才能被排除为最大值候选。

每次比较最多产生一个“输者”，所以至少需要：

n - 1

次比较才能找出最大值。

这也是普通扫描找最大值的比较次数，因此找最大值的最坏情况复杂度下界是紧的。

考点2：同时求最大值和最小值

算法思想

根据 07-Selection.ppt 第 7 页，同时求最大值和最小值可以通过两两分组减少比较次数。

算法步骤：

先把元素两两配对比较。
每组较大的元素进入最大值候选集合。
每组较小的元素进入最小值候选集合。
在最大值候选集合中找最大值。
在最小值候选集合中找最小值。

比较次数

若 $n$ 为偶数，第一次分组比较次数为：

\frac{n}{2}

最大值候选集合有 $\frac{n}{2}$ 个元素，找最大值需要：

\frac{n}{2} - 1

最小值候选集合也有 $\frac{n}{2}$ 个元素，找最小值需要：

\frac{n}{2} - 1

总比较次数为：

\frac{n}{2} + (\frac{n}{2} - 1) + (\frac{n}{2} - 1) = \frac{3 n}{2} - 2

若 $n$ 为奇数，课件给出的比较次数为：

⌈ \frac{3 n}{2} ⌉ - 2

对抗策略下界

07-Selection.ppt 第 8-10 页用信息单位解释下界。

要确定最大值，需要知道除最大值外，每个元素都输过一次。要确定最小值，需要知道除最小值外，每个元素都赢过一次。

因此总共需要获得：

2 n - 2

个信息单位。

对抗者可以把每个元素的状态分为：

$N$ ：还没有赢过，也没有输过。
已经赢过：不可能是最小值，但仍可能是最大值。
已经输过：不可能是最大值，但仍可能是最小值。

对抗策略的原则是：

如果两个元素都是 $N$ ，比较后一个赢、一个输，算法得到 $2$ 个新信息单位。
如果不是两个 $N$ 相比，对抗者尽量只让算法得到 $1$ 个新信息单位。

当 $n$ 为偶数时，最多只有最开始的 $\frac{n}{2}$ 次配对比较能贡献 $2$ 个信息单位。其余还需要：

(2 n - 2) - 2 \cdot \frac{n}{2} = n - 2

个信息单位，每次比较最多给 $1$ 个。

所以比较次数下界为：

\frac{n}{2} + (n - 2) = \frac{3 n}{2} - 2

这与前面的算法比较次数一致，因此该算法是最优的。

考点3：求第二大元素

朴素方法

根据 07-Selection.ppt 第 12 页，直接调用两次找最大值可以求第二大元素：

第一次找最大值。
删除最大值。
第二次在剩余元素中找最大值，也就是原集合的第二大元素。

比较次数为：

(n - 1) + (n - 2) = 2 n - 3

这个方法正确，但没有充分利用第一次找最大值过程中得到的信息。

锦标赛法

07-Selection.ppt 第 13-14 页给出更优方法：锦标赛法。

算法思想：

像淘汰赛一样两两比较，较大者晋级。
最终冠军就是最大值。
第二大元素只可能出现在“直接输给最大值”的元素中。
在这些直接输给最大值的元素中再找最大值。

直观原因是：如果某个元素输给的不是最大值，那么它至少输给了一个非最大元素，因此不可能是第二大。

比较次数

找最大值的锦标赛需要：

n - 1

次比较。

最大值从叶子一路晋级到根，最多直接打败：

⌈ lo g n ⌉

个元素。

第二大元素只可能在这些候选者中，所以再找最大需要：

⌈ lo g n ⌉ - 1

次比较。

总比较次数为：

n - 1 + ⌈ lo g n ⌉ - 1 = n + ⌈ lo g n ⌉ - 2

若 $n$ 是 $2$ 的幂，则最大值直接比较过的元素个数正好是：

lo g n

对抗策略下界

07-Selection.ppt 第 15-17 页说明，任何比较算法求第二大元素，在最坏情况下都至少需要：

n + ⌈ lo g n ⌉ - 2

次比较。

证明思路：

要找第二大，必须先确定最大值，因此至少需要 $n - 1$ 次比较。
第二大元素只能是直接输给最大值的元素。
对抗者可以迫使最大值至少直接赢过 $⌈ lo g n ⌉$ 个不同元素。
要从这 $⌈ lo g n ⌉$ 个候选者里找最大，还需要 $⌈ lo g n ⌉ - 1$ 次比较。

课件中的权重法可以理解为：

每个元素初始权重为 $1$ 。
当某个元素赢过一个此前没有输过的元素时，它的权重最多翻倍。
如果最终 $x$ 是最大值，它必须成为唯一仍可能是最大值的元素，因此它的权重需要达到 $n$ 。

若最大值经历了 $K$ 次这种关键胜利，则：

n \leq 2^{K}

所以：

K \geq ⌈ lo g n ⌉

因此最大值至少直接击败过 $⌈ lo g n ⌉$ 个候选者。算法必须在这些候选者中继续找最大，所以下界与锦标赛算法一致，锦标赛法是最优的。

08. 线性时间选择算法的实现和应用

复习资料

07-Selection.ppt 第 19-27 页：选择算法、划分策略、中位数的中位数、最坏情况线性复杂度
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：选择问题和第 k 大值转换

选择问题

根据 07-Selection.ppt 第 22 页，选择问题是：

给定集合 $S$ ，其中有 $n$ 个关键字，再给定整数 $k$ ，满足：

1 \leq k \leq n

要求找出 $S$ 中第 $k$ 小的关键字。

中位数选择只是选择问题的特殊情况：

k = ⌈ \frac{n}{2} ⌉

第 k 大和第 k 小的转换

课件默认讨论第 $k$ 小。如果题目问“第 $k$ 大”，可以转换成第几小。

在 $n$ 个元素中，第 $k$ 大等价于第：

n - k + 1

小。

例如在 $10$ 个元素中：

第 $1$ 大是第 $10$ 小。
第 $2$ 大是第 $9$ 小。
第 $k$ 大是第 $10 - k + 1$ 小。

所以求第 $k$ 大时，可以调用选择算法：

select (S, n - k + 1)

为什么只递归一边

07-Selection.ppt 第 19-20 页说明，如果能把集合划分成两个子集 $S_{1}$ 和 $S_{2}$ ，并满足：

\forall x \in S_{1}, \forall y \in S_{2}, x < y

那么目标元素只会落在其中一边。

若要找第 $k$ 小：

如果 $k \leq ∣ S_{1} ∣$ ，答案在 $S_{1}$ 中。
如果 $k = ∣ S_{1} ∣ + 1$ ，答案就是 pivot。
如果 $k > ∣ S_{1} ∣ + 1$ ，答案在 $S_{2}$ 中，并且新的排名变为：

k - ∣ S_{1} ∣ - 1

因此选择问题和快速排序不同：快速排序要递归左右两边，而选择算法只递归一边。

考点2：线性时间选择算法

坏 pivot 的问题

07-Selection.ppt 第 21-22 页指出，如果 pivot 很差，划分会非常不均匀，递归规模可能接近 $n - 1$ ，这会让选择算法退化。

所以线性时间选择算法的关键是：构造一个足够好的 pivot，使每轮至少丢掉固定比例的元素。

Median of Medians 思想

07-Selection.ppt 第 23-24 页给出的改进策略是中位数的中位数。

步骤如下：

将所有元素每 $5$ 个分为一组。
在每组内部排序。
找出每组的中位数。
递归地在这些组中位数中找中位数，记为 $m^{*}$ 。
用 $m^{*}$ 作为 pivot 对原集合划分。

这里的 $m^{*}$ 就是 median of medians。

构造划分

用 $m^{*}$ 作为 pivot 后，把元素划分为：

S_{1} = x ∣ x < m^{*}

S_{2} = x ∣ x > m^{*}

课件第 24 页用图中区域说明：由于 $m^{*}$ 是组中位数的中位数，至少有相当一部分元素能确定小于 $m^{*}$ ，也至少有相当一部分元素能确定大于 $m^{*}$ 。

这保证了递归处理的一边不会太大，最坏情况下大约不超过：

0.7 n + 2

递归过程

根据 07-Selection.ppt 第 25 页：

若要找第 $k$ 小，划分后：

{k = ∣ S_{1} ∣ + 1, 返回 m^{*} k \leq ∣ S_{1} ∣, 递归调用 select (S_{1}, k) k > ∣ S_{1} ∣ + 1, 递归调用 select (S_{2}, k - ∣ S_{1} ∣ - 1)

也就是说，每轮只进入一个子问题。

伪代码结构

select (S, k) : if ∣ S ∣ \leq 5, return direct solution divide S into groups of 5 find the median of each group m^{*} = select (group medians, ⌈ ∣ group medians ∣/2 ⌉) partition S into S_{1}, m^{*}, S_{2} if k = ∣ S_{1} ∣ + 1, return m^{*} else if k \leq ∣ S_{1} ∣, return select (S_{1}, k) else return select (S_{2}, k - ∣ S_{1} ∣ - 1)

考点3：复杂度分析和应用

比较次数来源

根据 07-Selection.ppt 第 26 页，线性选择算法每轮主要有三部分代价：

每 $5$ 个元素一组，找每组中位数。
递归找这些组中位数的中位数。
用 $m^{*}$ 对原集合做划分。

因此递推式可以写成：

W (n) \leq W (n /5) + W (0.7 n + 2) + c n

其中：

$W (n /5)$ ：递归寻找中位数的中位数。
$W (0.7 n + 2)$ ：最坏情况下，继续递归处理较大的那一边。
$c n$ ：分组、组内处理、划分等线性代价。

常见教材也会把它写成近似形式：

W (n) \leq W (n /5) + W (7 n /10) + O (n)

为什么是线性

07-Selection.ppt 第 27 页用递归树行和说明该递推式是线性的。

两条递归分支规模加起来大约是：

\frac{n}{5} + 0.7 n = 0.9 n

所以下一层的总规模至多约为上一层的 $0.9$ 倍。递归树每层线性代价形成递减几何级数：

c n + c (0.9 n) + c (0. 9^{2} n) + \dots

该级数和为：

c n i = 0 \sum \infty 0. 9^{i} = 10 c n

因此：

W (n) = Θ (n)

这就是“最坏情况下线性时间选择算法”的核心结论。

应用

线性时间选择算法可以用于：

找第 $k$ 小元素。
找第 $k$ 大元素。
找中位数。
找分位数。
找阈值，例如保留较小的一半、删除较大的一半。

例如，要找第 $k$ 大元素，可以先转换成第 $n - k + 1$ 小：

select (S, n - k + 1)

要删除较大的一半，可以先在线性时间内找出中位数，再用一次线性扫描删除大于中位数的元素。总时间仍为：

O (n)

09. 平摊分析、MultiPop Stack、DeleteLargerHalf 和栈模拟队列

复习资料

08-HashTable.ppt 第 15-20 页：数组扩张和平摊分析、MultiPop Stack
Amortized Analysis.pdf：平摊分析补充例题
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：平摊分析的含义

基本思想

平摊分析研究的是一串操作的总成本，而不是只看单次操作的最坏成本。

如果一个数据结构中存在某些“偶尔很贵”的操作，单独看最坏情况可能会把复杂度估得过高。平摊分析会把这些少数高成本操作分摊到整个操作序列上，得到每次操作的平均保证。

设一串操作共有 $m$ 次，实际总代价为：

T (m)

则单次操作的平摊代价可以理解为：

\frac{T ( m )}{m}

注意：平摊分析不是概率分析，不要求输入随机，也不取期望。它给的是任意操作序列上的总成本保证。

适用场景

平摊分析适合以下情况：

单次操作最坏情况很贵。
贵操作不可能连续频繁发生。
贵操作之前通常积累了很多便宜操作。
可以证明一串操作的总成本较低。

08-HashTable.ppt 第 15-18 页的数组扩张就是典型例子：某次插入触发扩容，需要搬移很多元素，但扩容只在容量满时发生，不能每次都发生。

常见分析方法

常见方法有三种：

聚合分析：直接证明 $m$ 次操作的总成本是 $T (m)$ ，再除以 $m$ 。
记账法：给便宜操作多收一些“代币”，以后用这些代币支付贵操作。
势能法：定义数据结构的势能 $Φ$ ，把未来可能发生的成本存进势能中。

课件第 18 页给出记账法的表达式：

amortized cost = actual cost + accounting cost

设计平摊代价时，要保证账户或势能不会欠债，这样总平摊成本才能覆盖总实际成本。

考点2：MultiPop Stack

操作定义

栈支持三个操作：

Push(x)：把元素 $x$ 压栈。
Pop()：弹出栈顶元素。
MultiPop(k)：连续弹出最多 $k$ 个元素，若栈中元素少于 $k$ 个，则弹到空栈为止。

若当前栈大小为 $s$ ，则：

cost (MultiPop (k)) = min (s, k)

所以单次 MultiPop(k) 的最坏情况可能是 $O (n)$ 。

聚合分析

考虑任意一串栈操作。每个元素最多经历：

被 Push 入栈一次。
被 Pop 或 MultiPop 弹出一次。

元素一旦被弹出，就不会再为之后的弹出操作付费。

如果一共执行 $m$ 次操作，那么压栈次数至多为 $m$ ，弹出元素总数也至多为 $m$ 。因此总成本为：

O (m)

所以每次操作的平摊成本为：

O (1)

记账法

08-HashTable.ppt 第 19 页给出一种记账方式：

Push 的平摊成本记为 $2$ 。
Pop 和 MultiPop 的平摊成本记为 $0$ 。

解释：

Push 实际花费 $1$ ，多收的 $1$ 个代币存在被压入的元素上。
以后该元素被 Pop 或 MultiPop 弹出时，用它身上的代币支付弹出成本。
每个元素只会被弹出一次，所以代币足够。

因此 Push、Pop、MultiPop 的平摊复杂度都是：

O (1)

考点3：DeleteLargerHalf

问题描述

维护一个集合 $S$ ，支持：

Insert(S,x)：插入元素 $x$ 。
DeleteLargerHalf(S)：删除集合中较大的一半元素。

如果当前集合大小为 $n$ ，DeleteLargerHalf 会删除大约：

⌊ \frac{n}{2} ⌋

个较大元素。

实现思路

可以借助第 8 章的线性时间选择算法：

用 select 在线性时间内找到中位数附近的阈值。
扫描集合，把大于阈值的一半元素删除。
保留较小的一半元素。

一次 DeleteLargerHalf 的实际成本可以记为：

O (n)

平摊分析

虽然单次 DeleteLargerHalf 可能很贵，但它会一次删除当前集合的一半元素。

可以使用记账法：

每次 Insert 多收常数个代币，存在新插入元素身上。
当元素在某次 DeleteLargerHalf 中被删除时，用它之前存下的代币支付删除和扫描的一部分成本。
一个元素从插入到被删除，最多只会被删除一次。

因此，在一串操作中，删除成本可以由之前插入的元素支付。

若共有 $m$ 次操作，则总成本为：

O (m)

所以每次操作的平摊成本为：

O (1)

这里要注意：如果实现中每次删除都用线性选择找到阈值，那么这次线性扫描成本被当前集合中即将保留和删除的元素共同承担。由于删除操作会显著减少集合规模，后续必须经过足够多次插入，集合规模才会再次变大。

考点4：两个栈模拟队列

实现方法

用两个栈实现队列：

输入栈 Stack_in：负责入队。
输出栈 Stack_out：负责出队。

入队 Enqueue(x)：

Push (Stac k_{i} n, x)

出队 Dequeue()：

如果 Stack_out 非空，直接从 Stack_out 弹出。
如果 Stack_out 为空，把 Stack_in 中所有元素依次弹出并压入 Stack_out。
再从 Stack_out 弹出队首元素。

为什么顺序正确

栈是后进先出。元素先进入 Stack_in，当整体搬运到 Stack_out 时，顺序会反转一次。

一次反转后，最早进入队列的元素会位于 Stack_out 栈顶，因此出队顺序正好符合先进先出。

平摊分析

每个元素最多经历以下栈操作：

压入 Stack_in 一次。
从 Stack_in 弹出一次。
压入 Stack_out 一次。
从 Stack_out 弹出一次。

因此每个元素最多参与常数次基本栈操作。

若一共处理 $m$ 个入队和出队操作，总成本为：

O (m)

所以单次队列操作的平摊成本为：

O (1)

10. 深度优先、广度优先和图上搜索问题

复习资料

10-DAGApp.ppt 第 5-34 页：DAG、拓扑序、任务调度、关键路径、强连通分量
09-GTraverse.ppt：DFS 和 BFS 基本思想
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：DFS 和 BFS 的思想

DFS

深度优先搜索的思想是：从一个顶点出发，沿着未访问的边尽量向深处走；当当前顶点没有未访问邻接点时，再回溯。

DFS 常用颜色标记：

白色：尚未发现。
灰色：已经发现，但邻接点还没有处理完。
黑色：已经处理完成。

DFS 中常记录：

发现时间。
完成时间。
父节点。
DFS 树或森林。

很多有向图算法依赖 DFS 的完成时间，例如拓扑排序和强连通分量。

BFS

广度优先搜索的思想是：从源点开始，按距离层次一层一层向外扩展。

BFS 通常使用队列：

源点入队。
每次取出队首顶点。
把它尚未访问的邻接点加入队尾。
重复直到队列为空。

BFS 适合解决：

无权图最短路径。
层次遍历。
可达性判断。

复杂度

若图用邻接表表示，DFS 和 BFS 都会访问每个顶点和每条边常数次，所以复杂度为：

Θ (n + m)

其中 $n = ∣ V ∣$ ， $m = ∣ E ∣$ 。

考点2：拓扑排序和任务调度

DAG 和拓扑序

根据 10-DAGApp.ppt 第 5-6 页，DAG 是有向无环图。

给定有向图：

G = (V, E)

拓扑序是给每个顶点分配不同编号 $1, 2, \dots, n$ ，使得对于每条有向边：

v w \in E

都有：

topo (v) < topo (w)

也就是说，边的起点必须排在终点前面。

何时存在拓扑序

10-DAGApp.ppt 第 7 和第 12 页说明：

G 有拓扑序 ⟺ G 是 DAG

如果图中有有向环，那么环上的顶点需要互相排在对方前面，会产生矛盾，因此不存在拓扑序。

DFS 求拓扑序

课件第 8-11 页给出基于 DFS 的反向拓扑序算法。

核心思想：

对图做 DFS。
在顶点完成时进行后序处理。
完成时间越晚的顶点，在拓扑序中越靠前。

若使用计数器 topoNum 在后序阶段递增，则得到的是反向拓扑序。若想得到普通拓扑序，可以按完成时间递减排列。

复杂度为：

Θ (n + m)

任务调度

10-DAGApp.ppt 第 13-14 页把任务调度建模为 DAG。

建模方式：

顶点表示任务。
有向边表示依赖关系。
若任务 $v$ 依赖任务 $w$ ，则必须先完成 $w$ 再做 $v$ 。

只要依赖图是 DAG，就可以按拓扑序安排任务。若依赖图有环，则任务之间存在循环依赖，无法完成合法调度。

考点3：关键路径

基本概念

10-DAGApp.ppt 第 15-17 页介绍关键路径。它适用于带任务时长的 DAG 项目网络。

对任务 $v$ ：

$est (v)$ ：最早开始时间。
$eft (v)$ ：最早完成时间。
$duration (v)$ ：任务耗时。

若 $v$ 没有依赖，则：

est (v) = 0

若 $v$ 有依赖，则：

est (v) = w \in p r e d (v) max eft (w)

并且：

eft (v) = est (v) + duration (v)

关键路径含义

关键路径是决定整个项目完成时间的一条任务链。

如果关键路径上的任务延迟，整个项目会延迟；如果减少非关键路径任务时间，通常不能缩短总工期。

项目最短完成时间为：

v \in V max eft (v)

DFS 计算关键路径

课件第 18-23 页给出 DFS 版本的关键路径算法。

需要维护：

duration[v]：任务时长。
eft[v]：最早完成时间。
critDep[v]：使 $v$ 最晚开始的关键依赖。

在 DFS 回溯或检查已完成邻接点时，用依赖任务的 eft 更新当前任务的 est：

est (v) = max (est (v), eft (w))

如果 $w$ 让当前最大值更新，则：

critDep (v) = w

最后：

eft (v) = est (v) + duration (v)

复杂度与 DFS 相同：

Θ (n + m)

考点4：强连通分量

定义

在有向图中，如果一个顶点集合内任意两个顶点都互相可达，并且这个集合不能再扩大，则它是一个强连通分量。

强连通分量缩成点之后得到的凝聚图一定是 DAG。

转置图

10-DAGApp.ppt 第 25 页介绍转置图 $G^{T}$ 。

转置图把原图中每条边方向反过来：

(u, v) \in E \Rightarrow (v, u) \in E^{T}

原图和转置图有相同的强连通分量，只是分量之间边的方向反了。

Kosaraju 算法

根据课件第 30-31 页，强连通分量算法分两阶段：

在原图 $G$ 上做 DFS，在每个顶点完成时把它压入栈 finishStack。
构造转置图 $G^{T}$ 。
按 finishStack 的弹出顺序，在 $G^{T}$ 上做 DFS。
第二阶段中每棵 DFS 树对应一个强连通分量。

为什么按完成时间逆序

第一阶段完成时间较晚的顶点，会在第二阶段更早被处理。

在转置图上从这样的顶点开始 DFS，可以刚好收集它所在的强连通分量，而不会越过到其它尚未处理的分量。

课件第 33-34 页给出的正确性思路是：

每次从栈中弹出的白色顶点，是某个强连通分量的 leader。
第二阶段从该 leader 出发的 DFS 树，恰好包含一个完整强连通分量。

算法复杂度为：

Θ (n + m)

11. 贪心法的思想和特点、换硬币和单源最短路径

复习资料

12-Greedy.ppt 第 4-7 页、第 25-26 页：贪心思想、换硬币反例、Dijkstra
第4章贪心算法.ppt 第 1 页、第 10-12 页、第 27-31 页：贪心基本要素、单源最短路径
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：贪心法的思想和特点

基本思想

贪心算法总是在当前状态下作出看起来最好的选择。

也就是说，它不直接从整体最优出发穷举所有方案，而是一步一步扩展部分解，每一步都选一个局部最优的候选。

12-Greedy.ppt 第 7 页把贪心选择描述为三个要求：

可行：选择后仍满足问题约束。
局部最优：在当前可行选择中最好。
不可撤销：一旦选入，后续不再反悔。

贪心算法框架

贪心算法通常可以写成：

S = \emptyset while S is not a solution and candidates are not empty: select a locally optimal candidate x remove x from candidates if x is feasible, add x to S

最后如果 $S$ 构成解，就返回 $S$ 。

两个基本要素

根据 第4章贪心算法.ppt 第 10-12 页，能用贪心法求最优解的问题通常具有两个性质：

贪心选择性质。
最优子结构性质。

贪心选择性质指：整体最优解可以通过一系列局部最优选择得到。

最优子结构性质指：问题的最优解包含其子问题的最优解。

为什么需要证明

贪心算法不总是正确。12-Greedy.ppt 第 6 页给出换硬币反例：

若硬币面值为：

1, 5, 12

要支付 $15$ ，贪心会选择：

12 + 1 + 1 + 1

共 $4$ 枚硬币。但最优解是：

5 + 5 + 5

只需要 $3$ 枚硬币。

所以贪心题不能只写算法，还要说明为什么局部最优选择能导向全局最优。

考点2：换硬币

问题描述

给定若干面值的硬币，每种硬币数量足够多，要求用尽可能少的硬币凑出金额 $n$ 。

常见贪心策略是：

每次选择不超过剩余金额的最大面值硬币。
从剩余金额中扣除该面值。
重复直到剩余金额为 $0$ 。

贪心不一定适用

对于一般硬币系统，贪心不一定最优。

例如：

1, 5, 12, n = 15

贪心得到 $12 + 1 + 1 + 1$ ，但最优是 $5 + 5 + 5$ 。

因此考试中如果要求证明，必须结合特定硬币系统说明贪心成立。

特殊面值系统

若硬币面值为：

A_{n} = c^{0}, c^{1}, \dots, c^{n - 1}

即：

1, c, c^{2}, \dots, c^{n - 1}

则贪心策略是最优的。

证明思路

在任意最优解中，低一档硬币的数量不能达到 $c$ 。

原因是：如果有 $c$ 枚面值为 $c^{i}$ 的硬币，那么它们可以替换成 $1$ 枚面值为 $c^{i + 1}$ 的硬币：

c \cdot c^{i} = c^{i + 1}

替换后总金额不变，但硬币数从 $c$ 枚变成 $1$ 枚，硬币数更少。这与“最优解使用硬币数最少”矛盾。

所以在最优解中，每个低面值硬币的数量都小于 $c$ 。

这说明最高面值硬币应尽可能多取，且这个选择与贪心一致。取完最高面值硬币后，剩余金额仍是同类子问题，可以递归证明后续选择也与贪心一致。

考点3：单源最短路径

问题描述

根据 第4章贪心算法.ppt 第 27 页，单源最短路径问题是：

给定带权有向图：

G = (V, E)

每条边权为非负实数，并给定源点 $s$ 。要求计算从 $s$ 到其他所有顶点的最短路径长度。

Dijkstra 算法适用于：

所有边权非负

算法思想

Dijkstra 算法维护一个集合 $S$ ：

S = 最短距离已经确定的顶点

初始时：

S = s

并维护数组 dist，其中 dist[v] 表示当前从源点到 $v$ 的最短特殊路径长度。

每一步执行：

从 $V - S$ 中选择 dist 最小的顶点 $u$ 。
把 $u$ 加入 $S$ 。
用 $u$ 的出边更新其他顶点的 dist，即松弛操作。

松弛公式为：

dist (v) = min dist (v), dist (u) + w (u, v)

贪心选择为什么成立

每次选择 $V - S$ 中 dist 最小的顶点 $u$ 。

由于所有边权非负，任何从源点绕道其他未确定顶点再到 $u$ 的路径，都不可能比当前最小的 dist[u] 更短。

因此一旦 $u$ 被选中，它的最短路径长度就可以确定，之后不会再变小。

这正是 Dijkstra 的贪心选择性质。

复杂度

若用邻接矩阵和简单数组实现，每轮扫描所有未确定顶点找最小 dist，总复杂度通常为：

O (n^{2})

若用优先队列维护未确定顶点，复杂度取决于堆实现，常见写法为：

O ((n + m) lo g n)

其中 $n = ∣ V ∣$ ， $m = ∣ E ∣$ 。

12. 动态规划的思想和经典问题

复习资料

第3章动态规划.ppt 第 1-21 页：动态规划思想、最优子结构、重叠子问题、最长公共子序列
13-DynamProg.ppt 第 4-9 页：递归、子问题图、动态规划基本思想
DynamicProgrammingReview.pdf
高级算法期末复习录音.docx
2026高级算法复习.pdf

考点1：动态规划的思想和特点

基本思想

动态规划和分治法一样，都会把原问题分解为子问题。

区别在于：动态规划中的子问题通常不是互相独立的，不同递归分支可能反复遇到同一个子问题。

因此，动态规划的核心是：

每个子问题只计算一次，并保存结果

之后再遇到同一子问题时，直接查表。

两个关键性质

根据 第3章动态规划.ppt 第 14-15 页，动态规划通常依赖两个性质：

最优子结构。
重叠子问题。

最优子结构指：原问题的最优解包含子问题的最优解。

重叠子问题指：递归求解时，许多子问题会被反复计算。

解题步骤

动态规划题通常按以下顺序写：

定义状态。
写状态转移方程。
写边界条件。
确定填表顺序。
描述算法或伪代码。
分析时间复杂度和空间复杂度。

子问题图视角

13-DynamProg.ppt 第 5-7 页把子问题看成一个 DAG。

顶点表示子问题。
边表示一个子问题依赖另一个子问题。
动态规划就是按依赖顺序计算这些顶点。

如果按反向拓扑序计算，就可以保证计算某个状态时，它依赖的子状态已经求出。

考点2：最长公共子序列

问题描述

给定两个序列：

X = x_{1}, x_{2}, \dots, x_{m}

Y = y_{1}, y_{2}, \dots, y_{n}

要求找出它们的最长公共子序列。

子序列不要求连续，只要求相对顺序保持不变。

状态定义

令：

L [i] [j] = X [1.. i] 和 Y [1.. j] 的最长公共子序列长度

目标是求：

L [m] [n]

状态转移

根据 第3章动态规划.ppt 第 18-20 页：

若：

x_{i} = y_{j}

则这两个字符可以作为公共子序列的最后一个字符：

L [i] [j] = L [i - 1] [j - 1] + 1

若：

x_{i} \neq = y_{j}

则最后一个字符不可能同时取二者，只能丢掉一个前缀末尾：

L [i] [j] = max L [i - 1] [j], L [i] [j - 1]

合并写成：

L [i] [j] = {L [i - 1] [j - 1] + 1, x_{i} = y_{j} max L [i - 1] [j], L [i] [j - 1], x_{i} \neq = y_{j}

边界和复杂度

当某个序列为空时，最长公共子序列长度为 $0$ ：

L [0] [j] = 0, L [i] [0] = 0

状态数为：

mn

每个状态 $O (1)$ 计算，因此时间复杂度为：

O (mn)

空间复杂度为：

O (mn)

若只求长度，可以滚动数组优化到：

O (min m, n)

考点3：抽牌拿取最大值

问题描述

有一排牌：

c a r d s [1.. n]

两名玩家轮流从最左端或最右端取一张牌，双方都采取最优策略。常见问题是求先手最多能获得多少收益，或先手相对后手的最大净胜分。

差值状态

定义：

D [i] [j] = 当前玩家面对 c a r d s [i .. j] 时，相对对手的最大净胜分

这里用“当前玩家”而不是固定先手，是为了让子问题保持同一种含义。

状态转移

当前玩家有两个选择：

取左端牌 $c a r d s [i]$ ，之后对手面对 $c a r d s [i + 1.. j]$ 。
取右端牌 $c a r d s [j]$ ，之后对手面对 $c a r d s [i .. j - 1]$ 。

如果当前玩家取左端，则净胜分为：

c a r d s [i] - D [i + 1] [j]

如果当前玩家取右端，则净胜分为：

c a r d s [j] - D [i] [j - 1]

所以：

D [i] [j] = max c a r d s [i] - D [i + 1] [j], c a r d s [j] - D [i] [j - 1]

边界和复杂度

当只剩一张牌时：

D [i] [i] = c a r d s [i]

填表时按区间长度从小到大计算。

状态数量为：

O (n^{2})

每个状态 $O (1)$ 转移，因此：

时间复杂度 = O (n^{2}), 空间复杂度 = O (n^{2})

考点4：回文判断和分割问题

回文判断

定义：

P [i] [j] = s [i .. j] 是否为回文串

若两端字符相同，并且中间部分也是回文，则整体是回文。

状态转移：

P [i] [j] = (s [i] = s [j]) \land (j - i \leq 2 \lor P [i + 1] [j - 1])

其中：

$j - i \leq 2$ 表示长度为 $1$ 、 $2$ 或 $3$ 的短串，只要两端相等即可。
长串需要继续检查内部子串。

填表顺序通常按子串长度从小到大。

最小回文分割

定义：

c u t [i] = s [1.. i] 的最少分割次数

如果整个前缀 $s [1.. i]$ 本身就是回文，则：

c u t [i] = 0

否则枚举最后一段回文串的起点 $j + 1$ ：

c u t [i] = min c u t [j] + 1 ∣ P [j + 1] [i] = t r u e

完整写法：

c u t [i] = {0, P [1] [i] = t r u e min c u t [j] + 1 ∣ P [j + 1] [i] = t r u e, P [1] [i] = f a l se

最长回文子序列

如果考的是最长回文子序列，可以定义：

T [i] [j] = s [i .. j] 的最长回文子序列长度

若：

s [i] = s [j]

则：

T [i] [j] = 2 + T [i + 1] [j - 1]

若：

s [i] \neq = s [j]

则：

T [i] [j] = max T [i + 1] [j], T [i] [j - 1]

边界为：

T [i] [i] = 1

回文类区间 DP 的共同点是：状态通常定义在区间 $[i, j]$ 上，填表顺序通常按区间长度递增。

目录

01. 算法的最坏复杂度、平均复杂度和最优性

复习资料

考点1：最坏复杂度

考点2：平均复杂度

考点3：最优性

例子：从 n 个数中找最大值

02. 大 O、大 Ω、大 Θ 的定义和相关函数证明

复习资料

考点1：什么是大O、大Ω、大Θ

考点2：大O、大Ω、大Θ的性质

传递性

对偶与对称性质

和式性质

常数因子可忽略

自反性

考点3：常见增长阶

03. 递归关系求解

复习资料

考点1：解二阶线性齐次递推

特征方程

解题步骤

斐波那契型例子

04. 平滑函数性质和主定理应用

复习资料

考点1：平滑函数性质

定义

作用

典型平滑函数

典型非平滑函数

考点2：应用主定理求解一般式

分治递推的一般形式

递归树深度与临界指数

行和思想

主定理三种情况

三种情况的例子

规整条件补充

从题意翻译递推式

05. 堆的定义、数组表示和堆操作

复习资料

考点1：堆的定义

堆结构

偏序树性质

堆的完整定义

考点2：用数组表示堆

为什么可以用数组表示

课件中的 1 下标表示

0 下标补充

考点3：实现堆操作

堆排序策略

deleteMax

fixHeap

fixHeap 的复杂度

建堆 constructHeap

建堆复杂度

06. 复用快排平均复杂度分析方法处理其他问题

复习资料

考点：复用快排平均复杂分析方法

讲解例子：快排平均比较次数

随机划分模型

平均比较次数递推式

根据递推式推出复杂度

可能考题1：螺丝螺母配对

问题描述

算法思想

递推式和复杂度

可能考题2：同学和衣服尺码匹配

问题描述

算法思想

递推式和复杂度

07. 对抗策略及经典选择问题下界

复习资料

考点1：对抗策略的含义

选择问题背景

下界证明的基本想法

找最大值的下界

考点2：同时求最大值和最小值

算法思想

比较次数

对抗策略下界

`deleteMax`

`fixHeap`

`fixHeap` 的复杂度

建堆 `constructHeap`