算法设计与分析归纳

参考资料为算法黑皮书和红皮书第四版，任教老师为邱德红，作者Bolaxious。这门课的重点并不在于讲为了实现某种算法要怎么去写代码，而是讲一讲算法背后的设计和考虑。课程主要内容都在上一篇文章复习材料中提到并做了扩展，这里则进一步简化

2021年考试题解答

根据题目要求，我们需要解答 2021 年的算法相关问题，并结合知识点进行分析。以下是针对每个问题的详细解答：

简述三种算法效率符号

知识点：算法时间复杂度分析

算法效率通常用大 O、Ω 和 Θ 符号来描述：

大 O 符号 (O)：
- 描述算法在最坏情况下的上界。
- 表示算法运行时间不会超过某个增长速率。
- 例如，如果一个算法的时间复杂度是 $O(n^2)$ ，表示其运行时间在最坏情况下不会超过 $n^2$ 的常数倍。
Ω 符号 (Ω)：
- 描述算法在最好情况下的下界。
- 表示算法运行时间至少会达到某个增长速率。
- 例如，如果一个算法的时间复杂度是 $\Omega(n)$ ，表示其运行时间在最好情况下至少是 $n$ 的常数倍。
Θ 符号 (Θ)：
- 描述算法在平均情况或确切情况下的紧确界。
- 表示算法运行时间既不会低于某个增长速率，也不会高于另一个增长速率。
- 例如，如果一个算法的时间复杂度是 $\Theta(n \log n)$ ，表示其运行时间在所有情况下都与 $n \log n$ 同阶。

总结

大 O：最坏情况的上界。
Ω：最好情况的下界。
Θ：平均或确切情况的紧确界。

两种随机化算法及特征

Las Vegas 算法

Las Vegas 算法是一类总是返回正确结果的随机化算法，但其运行时间是随机的。

核心特征：

结果正确。
运行时间不确定，可能因随机选择而变长或变短。

示例：

随机快速排序：每次划分的基准值是随机选取的，虽然运行时间可能不同，但最终结果始终有序。
随机化哈希查找：在冲突处理中使用随机探测策略。

时间复杂度：

通常分析其期望运行时间，例如 $O(n \log n)$ 。

Monte Carlo 算法

Monte Carlo 算法是一类运行时间固定或有界的随机化算法，但它可能返回错误的结果，不过可以通过多次运行来降低出错概率。

核心特征：

运行时间可预测。
结果可能不正确，但错误概率可以控制。

示例：

Miller-Rabin 素性测试：用于判断一个大整数是否为素数，有一定的误判率，但可通过多轮测试将错误概率降到极低。
Freivalds 算法：用于验证矩阵乘积是否正确，通过随机向量近似判断，具有一定的错误概率。

时间复杂度：

通常是固定的，如 $O(n^2)$ 或 $O(1)$ 。

总结

快速选择：基于随机 pivot 的分治算法，用于寻找第 k 小的元素。
哈希表：利用随机哈希函数实现高效的键值对存储和检索。

字符编码 & 文本文件最短储存，字符编码的特点

知识点：字符编码与文本压缩

字符编码：
- ASCII 编码：
  - 每个字符占用 8 位（1 字节），支持 256 种不同的字符。
  - 特点：简单、固定长度，但无法表示中文等多字节字符。
- Unicode 编码：
  - 支持全球范围内的字符集，包括中文、日文等。
  - 常见的 Unicode 编码方式有 UTF-8、UTF-16 等。
  - 特点：可变长度编码，兼容 ASCII，适合国际化需求。
文本文件最短储存：
- 霍夫曼编码（Huffman Coding）：
  - 根据字符出现频率动态分配码长，频率高的字符使用短码，频率低的字符使用长码。
  - 特点：无损压缩，适用于文本文件的高效存储。
- LZW 压缩（Lempel-Ziv-Welch Compression）：
  - 基于字典的压缩方法，通过构建字符串字典来减少重复数据。
  - 特点：适用于具有大量重复模式的文本文件。

总结

字符编码：ASCII 和 Unicode 是常用的字符编码方式，分别适用于简单的英文字符和国际化需求。
文本压缩：霍夫曼编码和 LZW 压缩是常用的文本压缩算法，能够有效减少存储空间。

分治法子问题的特点

知识点：分治法的核心思想

分治法（Divide and Conquer）的基本步骤包括：

分解（Divide）：
- 将原问题分解为若干个规模较小的子问题。
- 子问题应相互独立，且与原问题形式相同。
解决（Conquer）：
- 递归地求解各个子问题。
- 如果子问题足够小，则直接求解。
合并（Combine）：
- 将子问题的解合并为原问题的解。

子问题的特点：

独立性：
- 子问题之间没有重叠，可以并行求解。
同构性：
- 子问题与原问题具有相同的结构，便于递归求解。
可合并性：
- 子问题的解可以通过某种方式合并为原问题的解。

例子：归并排序（Merge Sort）

分解：将数组分成两半。
解决：递归地对两半分别排序。
合并：将两个有序子数组合并成一个有序数组。

总结

分治法的子问题应具备独立性、同构性和可合并性，以便高效地解决问题。

证明题：很简单的问题

知识点：算法正确性的证明

以快速选择算法为例，证明其正确性：

快速选择算法：
- 目标：在未排序数组中找到第 k 小的元素。
- 步骤：
  1. 随机选择一个 pivot。
  2. 将数组分为小于 pivot 的部分和大于 pivot 的部分。
  3. 根据 pivot 的位置判断目标元素在哪一部分，递归求解。
证明思路：
- 归纳法：
  - 假设对于大小为 $n-1$ 的数组，快速选择算法能正确找到第 k 小的元素。
  - 对于大小为 $n$ 的数组，随机选择 pivot 后，根据 pivot 的位置调整 k 的值，递归求解。
- 正确性保证：
  - 每次划分后，pivot 的位置确定了它在数组中的排名。
  - 根据 pivot 的位置，可以准确判断目标元素在左半部分还是右半部分。

总结

快速选择算法的正确性可以通过归纳法证明，关键在于每次划分后 pivot 的位置能够准确反映其排名。

设计题：分治法求 n 元素数组中数量超过一半的元素

知识点：Boyer-Moore 投票算法

问题描述：
- 在一个包含 $n$ 个元素的数组中，找出一个出现次数超过 $\frac{n}{2}$ 的元素（若存在）。
算法设计：
- Boyer-Moore 投票算法：
  1. 初始化候选者 candidate 和计数器 count。
  2. 遍历数组：
    - 如果当前元素等于 candidate，则 count++。
    - 如果当前元素不等于 candidate，则 count--。
    - 如果 count == 0，则更新 candidate 为当前元素。
  3. 验证 candidate 是否满足条件（即是否出现超过 $\frac{n}{2}$ 次）。
时间复杂度：
- 第一遍遍历数组： $O(n)$ 。
- 第二遍验证： $O(n)$ 。
- 总复杂度： $O(n)$ 。

总结

Boyer-Moore 投票算法是一种线性时间的分治思想应用，用于解决多数元素问题。

动态规划：批了一个称重外皮完全背包问题

知识点：完全背包问题

问题描述：
- 给定 $n$ 种物品，每种物品有无限供应，重量为 $w_i$ ，价值为 $v_i$ ，背包容量为 $W$ 。求装入背包的最大总价值。
动态规划状态定义：
- 设 $dp[i][j]$ 表示前 $i$ 种物品中，背包容量为 $j$ 时的最大价值。
- 状态转移方程： $dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + v_i)$
- 初始条件： $dp[0][j] = 0, \quad dp[i][0] = 0$
优化空间复杂度：
- 由于状态转移只依赖于当前行和上一行，可以用一维数组实现： $dp[j] = \max(dp[j], dp[j-w_i] + v_i)$

总结

完全背包问题可以通过动态规划解决，状态转移方程的关键在于允许重复选取同一种物品。

贪心：教室安排（原题）

知识点：区间调度问题

问题描述：
- 有多个教室安排请求，每个请求包含开始时间和结束时间，求最多能安排多少个不重叠的教室。
贪心策略：
- 按照结束时间从小到大排序。
- 依次选择结束时间最早的请求，只要其开始时间不早于当前已安排的最后一个请求的结束时间。
正确性证明：
- 贪心选择局部最优（最早结束的请求），全局最优（最多安排的请求）。
- 可以通过交换论证证明贪心策略的正确性。

总结

教室安排问题可以通过贪心算法解决，核心是按照结束时间排序并选择不重叠的区间。

图论：最大流和最小割 & 3 * 3 的 Floyd

知识点：最大流与最小割

最大流问题：
- 使用 Ford-Fulkerson 方法或 Edmonds-Karp 算法求解。
- 关键步骤：
  - 构建残余网络。
  - 寻找增广路径。
  - 更新流量直到找不到增广路径。
最小割问题：
- 最大流最小割定理：最大流的值等于最小割的容量。
- 可以通过最大流算法间接求解最小割。

知识点：Floyd-Warshall 算法

问题描述：
- 求解所有顶点对之间的最短路径。
- 输入是一个带权有向图，输出是一个 $n \times n$ 的矩阵，表示任意两点间的最短距离。
算法步骤：
- 初始化距离矩阵 $D$ 。
- 迭代更新： $D_{ij} = \min(D_{ij}, D_{ik} + D_{kj})$
- 时间复杂度： $O(n^3)$ 。

总结

最大流和最小割问题可以通过 Ford-Fulkerson 或 Edmonds-Karp 算法求解。
Floyd-Warshall 算法用于求解所有顶点对的最短路径，时间复杂度为 $O(n^3)$ 。

主方法（Master Method）的三种情况

主方法是一种用于求解形如 $T(n)=aT(n/b)+f(n)$ 的递归式的方法，其中：

$a \geq 1$ 和 $b > 1$ 是常数，
$f(n)$ 是一个渐进正函数。

主方法的核心是通过比较 $f(n)$ 和 $n^{\log_b a}$ 的增长速度来确定递归式的解。以下是三种情况的简洁说明：

1. 情况 1： $f(n)=O(n^{\log_b a-\epsilon})$

条件：存在某个常数 $\epsilon>0$ ，使得 $f(n)$ 的增长速度远慢于 $n^{\log_b a}$ 。
解释： $f(n)$ 被 $n^{\log_b a}$ 多项式地压制，即 $f(n)$ 的增长速度远远小于 $n^{\log_b a}$ 。
结果：递归式的解为：
$T(n) = \Theta(n^{\log_b a})$
直观理解：递归部分 $aT(n/b)$ 的贡献主导了整个递归式，因此解的阶取决于 $n^{\log_b a}$ 。

2. 情况 2： $f(n)=\Theta(n^{\log_b a})$

条件： $f(n)$ 的增长速度与 $n^{\log_b a}$ 相同。
解释： $f(n)$ 和 $n^{\log_b a}$ 的阶相同，即它们的增长速度相近。
结果：递归式的解为：
$T(n) = \Theta(n^{\log_b a} \log n)$
直观理解：递归部分和非递归部分 $f(n)$ 的贡献相当，因此解的阶需要额外乘以一个对数因子 $\log n$ 。

3. 情况 3： $f(n)=\Omega(n^{\log_b a+\epsilon})$

条件：存在某个常数 $\epsilon>0$ ，使得 $f(n)$ 的增长速度远快于 $n^{\log_b a}$ 。
解释： $f(n)$ 多项式地支配 $n^{\log_b a}$ ，即 $f(n)$ 的增长速度远远大于 $n^{\log_b a}$ 。
附加条件：还需满足"正则性条件"（regularity condition），即对于某个常数 $c<1$ 和所有足够大的 $n$ ，有：
$af(n/b) \leq cf(n)$
结果：递归式的解为：
$T(n) = \Theta(f(n))$
直观理解：非递归部分 $f(n)$ 的贡献主导了整个递归式，因此解的阶取决于 $f(n)$ 。

实例分析

考虑递归式：

$T(n) = 9T(n/3) + n$

参数： $a=9$ ， $b=3$ ， $f(n)=n$ 。
计算 $n^{\log_b a}$ ：
$n^{\log_3 9} = n^2$
比较 $f(n)=n$ $f (n) = n$ 和 $n^2$ $n 2 $ ：
- 显然， $f(n)=n$ 的增长速度远慢于 $n^2$ ，即 $f(n)=O(n^{2-\epsilon})$ （取 $\epsilon=1$ ）。
根据情况 1，递归式的解为：
$T(n) = \Theta(n^2)$

总结

情况	条件	结果
1	$f(n)=O(n^{\log_b a-\epsilon})$	$T(n)=\Theta(n^{\log_b a})$
2	$f(n)=\Theta(n^{\log_b a})$	$T(n)=\Theta(n^{\log_b a}\log n)$
3	$f(n)=\Omega(n^{\log_b a+\epsilon})$ 且满足正则性条件	$T(n)=\Theta(f(n))$

基于比较的排序算法的理论下界简要证明思路

我们使用**决策树（Decision Tree）**来分析比较排序的下界：

1. 决策树是什么？

决策树是一棵二叉树，表示排序算法在所有可能输入下的所有比较路径。
树中的每个内部节点表示一次比较（如 a < b），两个子节点表示比较结果（左为真，右为假）。
每个叶子节点代表一个可能的输出排列。

2. 有多少种可能的排列？

对于 n 个不同的元素，有 n! 种不同的排列方式。
所以决策树必须至少有 n! 个叶子节点。

3. 决策树的高度是多少？

一棵高度为 h 的二叉树最多有 $2^h$ 个叶子。
因此为了表示所有 n! 个排列，必须满足：
$2^h \geq n!$
取对数得：
$h \geq \log_2(n!)$

4. 估计 $\log_2(n!)$ 的下界

利用斯特林公式（Stirling's approximation）：

$\log_2(n!) = \Theta(n \log n)$

所以：

$h = \Omega(n \log n)$

✅ 结论

任何基于比较的排序算法，在最坏情况下至少需要 Ω(n log n) 次比较。
这意味着像归并排序和堆排序这样的算法已经是最优的（渐近意义上）。
快速排序的平均情况也是 Θ(n log n)，但在最坏情况下是 O(n²)。

6种排序算法比较和示例

当然可以！我们先将原表格中的 示例输入输出 去掉，再在表格下方分别给出每种排序算法的 具体实例说明。

排序算法对比表

排序算法	时间复杂度（最/平/最坏）	空间复杂度	是否稳定	是否原地	适用场景	简要分析
插入排序	$O(n)/O(n^2)/O(n^2)$	$O(1)$	✅	✅	小数组或基本有序数据	简单直观，适合小规模数据
归并排序	$O(n\log n)$ 均等	$O(n)$	✅	❌	大数据、需要稳定性的场合	分治策略，稳定且高效，但空间开销大
快速排序	$O(n\log n)/O(n\log n)/O(n^2)$	$O(\log n)$ ~ $O(n)$	❌	✅	一般排序首选算法	分治策略，平均最快，但最坏情况差
基数排序	$O(d(n+k))$	$O(n+k)$	✅	❌	固定位数整数或字符串	不基于比较，适合位数固定的数据
计数排序	$O(n+k)$	$O(k)$	✅	❌	整数范围较小的数据	高效但受范围限制
桶排序	平均 $O(n)$ ，最坏 $O(n^2)$	$O(n+k)$	✅	❌	浮点数、分布均匀的数据	数据分布影响性能

1. 插入排序（Insertion Sort）

例子：对 [5, 2, 4, 6, 1, 3] 进行排序
过程：
- 初始：[5, 2, 4, 6, 1, 3]
- 第一轮：[2, 5, 4, 6, 1, 3]
- 第二轮：[2, 4, 5, 6, 1, 3]
- 第三轮：[2, 4, 5, 6, 1, 3]
- 第四轮：[1, 2, 4, 5, 6, 3]
- 第五轮：[1, 2, 3, 4, 5, 6]

2. 归并排序（Merge Sort）

例子：对 [38, 27, 43, 3, 9, 82, 10] 进行排序
过程：
- 分解成单个元素：[38], [27], [43], [3], [9], [82], [10]
- 两两合并：[27, 38], [3, 43], [9, 82], [10]
- 继续合并：[3, 27, 38, 43], [9, 10, 82]
- 最终合并：[3, 9, 10, 27, 38, 43, 82]

3. 快速排序（Quick Sort）

例子：对 [5, 3, 8, 4, 2] 进行排序
过程：
- 选最后一个元素 2 作为 pivot，分区后左边为空，右边为 [5, 3, 8, 4]
- 对右边递归选择 pivot，比如选 4，分区为 [3] 和 [5, 8]
- 最终合并：[2, 3, 4, 5, 8]

4. 基数排序（Radix Sort）

例子：对 [170, 45, 75, 90, 802, 24, 2, 66] 进行排序
过程：
- 按个位排序：[170, 90, 802, 2, 24, 45, 75, 66]
- 按十位排序：[802, 2, 24, 45, 66, 170, 75, 90]
- 按百位排序：[2, 24, 45, 66, 75, 90, 170, 802]

5. 计数排序（Counting Sort）

例子：对 [4, 2, 2, 8, 3, 3, 1] 进行排序
过程：
- 创建计数数组，统计每个数字出现次数
- 按顺序还原：1 出现 1 次，2 出现 2 次，3 出现 2 次，4 出现 1 次，8 出现 1 次
- 输出结果：[1, 2, 2, 3, 3, 4, 8]

6. 桶排序（Bucket Sort）

例子：对 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21] 进行排序
过程：
- 创建 10 个桶，按小数点第一位分配数据
- 每个桶内排序（如使用插入排序）
- 合并所有桶数据得到最终有序序列：[0.17, 0.21, 0.26, 0.39, 0.72, 0.78, 0.94]

好的，以下是关于分治法及其开销的简要介绍，不再使用任何 emoji 或分割线。

分治法

分治法是一种重要的算法设计策略，其核心思想是：

将一个复杂的问题划分为若干个规模较小但结构相似的子问题，分别求解这些子问题，再将它们的解合并以得到原问题的解。

通常包括三个步骤：

划分（Divide）：将原问题分解为多个子问题。
求解（Conquer）：递归地解决每个子问题。当子问题足够小时，直接求解。
合并（Combine）：将子问题的解组合起来，形成原问题的解。

分治法的开销分析

分治法的时间复杂度通常可以用递归式来表示：

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

其中：

$n$ 是问题的规模，
$a \geq 1$ 是递归调用的子问题数量，
$b > 1$ 是子问题的规模缩小比例，
$ f(n)$ 是划分问题和合并解所需的额外时间。

可以使用主定理（Master Theorem）来分析这类递归式的渐进行为。

常见分治算法及时间复杂度

算法	分治方式	时间复杂度
归并排序	将数组分成两半，分别排序后合并	$T(n) = 2T(n/2) + O(n) \Rightarrow O(n \log n)$
快速排序	按基准值将数组划分为左右两部分	平均 $O(n \log n) $，最坏 $ O(n^2)$
二分查找	每次将搜索区间减半	$T(n) = T(n/2) + O(1) \Rightarrow O(\log n)$
快速幂	将指数不断减半计算幂值	$T(n) = T(n/2) + O(1) \Rightarrow O(\log n)$

优缺点分析

优点：

结构清晰，逻辑简单，易于理解和实现。
可以高效处理大规模数据。
支持并行化计算。

缺点：

递归可能带来较大的函数调用开销。
合并阶段有时会引入额外的时间或空间开销。
不一定适用于所有类型的问题。

好的，以下是关于二分搜索、标准定义与朴素分治矩阵乘法、Strassen矩阵乘法算法、大整数乘法、最近点对问题的简要介绍。每个内容均使用三级标题。

二分搜索

二分搜索是一种在有序数组中查找特定元素的高效算法。它通过不断将搜索区间减半来缩小可能的位置范围，直到找到目标值或确定其不存在。

算法思想：

比较中间元素与目标值。
如果相等，则返回中间位置。
如果中间元素大于目标值，则在左半部分继续搜索。
如果中间元素小于目标值，则在右半部分继续搜索。
重复上述步骤，直到找到目标或搜索区间为空。

时间复杂度：

最坏情况和平均情况均为 $O(\log n)$ 。

空间复杂度：

使用递归实现时为 $O(\log n)$ ，迭代实现为 $O(1)$ 。

标准定义与朴素分治矩阵乘法

矩阵乘法的标准定义是：对于两个 $n \times n$ 的矩阵 $A$ 和 $B$ ，它们的乘积 $C = AB$ 中的每个元素 $C[i][j]$ 是 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列对应元素乘积之和。

标准矩阵乘法定义：

对于 $n \times n$ 矩阵 $A$ 和 $B$ ，其乘积 $C = A \times B$ 中的元素计算为：

$C[i][j] = \sum_{k=0}^{n-1} A[i][k] \times B[k][j]$

其中 $0 \leq i, j < n$ 。

朴素分治策略详解：

分解步骤：将 $n \times n$ 矩阵划分为四个 $\frac{n}{2} \times \frac{n}{2}$ 的子矩阵：
$A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}, \quad B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}, \quad C = \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix}$
递归计算：根据矩阵乘法定义，子矩阵乘积为：
$C_{11} = A_{11}B_{11} + A_{12}B_{21}$
$C_{12} = A_{11}B_{12} + A_{12}B_{22}$
$C_{21} = A_{21}B_{11} + A_{22}B_{21}$
$C_{22} = A_{21}B_{12} + A_{22}B_{22}$
计算量分析：需要进行8次子矩阵乘法和4次子矩阵加法。

递归式推导：

子矩阵乘法： $8T(\frac{n}{2})$
矩阵加法： $O(n^2)$
总递归式： $T(n) = 8T(\frac{n}{2}) + O(n^2)$

时间复杂度：

根据主定理， $a=8$ , $b=2$ , $f(n)=O(n^2)$ ，有 $n^{\log_2 8} = n^3 > n^2$ ，属于第一种情况，因此： $T(n) = \Theta(n^{\log_2 8}) = \Theta(n^3)$

这与标准的三重循环实现的时间复杂度相同，说明朴素分治方法并未带来渐近性能提升。

Strassen矩阵乘法算法

Strassen算法是对矩阵乘法的一种优化，通过减少递归调用次数（从8次减到7次）来降低时间复杂度。关键在于巧妙构造中间矩阵，减少乘法运算次数。

算法详细步骤：

矩阵分块：与朴素分治相同，将矩阵 $A$ 和 $B$ 分为四个子矩阵。
计算七个中间矩阵：
$M_1 = (A_{11} + A_{22})(B_{11} + B_{22})$
$M_2 = (A_{21} + A_{22})B_{11}$
$M_3 = A_{11}(B_{12} - B_{22})$
$M_4 = A_{22}(B_{21} - B_{11})$
$M_5 = (A_{11} + A_{12})B_{22}$
$M_6 = (A_{21} - A_{11})(B_{11} + B_{12})$
$M_7 = (A_{12} - A_{22})(B_{21} + B_{22})$
组合计算结果矩阵：
$C_{11} = M_1 + M_4 - M_5 + M_7$
$C_{12} = M_3 + M_5$
$C_{21} = M_2 + M_4$
$C_{22} = M_1 - M_2 + M_3 + M_6$

正确性证明：

通过展开上述公式，可以验证结果与标准矩阵乘法相同：

$C_{11} = A_{11}B_{11} + A_{12}B_{21}$

$C_{12} = A_{11}B_{12} + A_{12}B_{22}$

$C_{21} = A_{21}B_{11} + A_{22}B_{21}$

$C_{22} = A_{21}B_{12} + A_{22}B_{22}$

计算量分析：

子矩阵乘法：7次（而非朴素分治的8次）
矩阵加减法：18次（比朴素分治的4次多）

递归式推导：

$T(n) = 7T\left(\frac{n}{2}\right) + O(n^2)$

时间复杂度：

根据主定理， $a=7$ , $b=2$ , $f(n)=O(n^2)$ ，有 $n^{\log_2 7} \approx n^{2.81} > n^2$ ，属于第一种情况，因此：

$T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})$

实际应用考量：

常数因子：虽然渐近复杂度更低，但Strassen算法的常数因子较大，在矩阵规模较小时可能不如标准算法高效。
实际应用阈值：通常在实际应用中，会设置一个阈值，当矩阵规模小于该阈值时，使用标准算法；大于该阈值时，使用Strassen算法。
数值稳定性：由于涉及更多的加减运算，Strassen算法在处理浮点数时可能导致更大的舍入误差。
进一步优化：Strassen算法后来被进一步改进，如Coppersmith-Winograd算法，理论复杂度可达到 $O(n^{2.376})$ ，但实际应用价值有限。

实例演示：

以两个 $2 \times 2$ 矩阵为例：

$A = \begin{pmatrix} 1 & 3 \\ 7 & 5 \end{pmatrix}, \quad B = \begin{pmatrix} 6 & 8 \\ 4 & 2 \end{pmatrix}$

计算七个中间矩阵：

$M_1 = (1+5)(6+2) = 6 \times 8 = 48$
$M_2 = (7+5)6 = 12 \times 6 = 72$
$M_3 = 1(8-2) = 1 \times 6 = 6$
$M_4 = 5(4-6) = 5 \times (-2) = -10$
$M_5 = (1+3)2 = 4 \times 2 = 8$
$M_6 = (7-1)(6+8) = 6 \times 14 = 84$
$M_7 = (3-5)(4+2) = (-2) \times 6 = -12$

计算结果矩阵：

$C_{11} = 48 + (-10) - 8 + (-12) = 18$
$C_{12} = 6 + 8 = 14$
$C_{21} = 72 + (-10) = 62$
$C_{22} = 48 - 72 + 6 + 84 = 66$

因此：

$C = \begin{pmatrix} 18 & 14 \\ 62 & 66 \end{pmatrix}$

可以验证，这与标准矩阵乘法得到的结果相同。

大整数乘法

大整数乘法用于处理超出机器字长限制的整数相乘问题。一种经典的方法是 Karatsuba 算法，它采用分治策略将乘法拆解为更少的递归乘法。

Karatsuba算法详解

基本思想

传统的大整数乘法需要 $O(n^2)$ 的时间复杂度，而Karatsuba算法通过减少乘法次数，将时间复杂度降至 $O(n^{\log_2 3}) \approx O(n^{1.585})$ 。

算法详细步骤

分解：将两个 $n$ 位大整数 $x$ 和 $y$ 分成两部分：
$x = a \cdot 10^{n/2} + b$
$y = c \cdot 10^{n/2} + d$
其中 $a$ , $b$ , $c$ , $d$ 都是约 $n/2$ 位的整数。
传统乘法：直接计算 $x \cdot y$ 需要四次乘法：
$x \cdot y = (a \cdot 10^{n/2} + b)(c \cdot 10^{n/2} + d) = ac \cdot 10^n + (ad + bc) \cdot 10^{n/2} + bd$
Karatsuba优化：只需三次乘法，通过以下步骤：
- 计算 $z_1 = a \cdot c$
- 计算 $z_3 = b \cdot d$
- 计算 $z_2 = (a+b)(c+d) - z_1 - z_3 = ac + ad + bc + bd - ac - bd = ad + bc$
合并结果：
$x \cdot y = z_1 \cdot 10^n + z_2 \cdot 10^{n/2} + z_3$

递归实现

function karatsuba(x, y):
    // 基本情况
    if x < 10 or y < 10:
        return x * y
        
    // 计算位数
    n = max(size(x), size(y))
    m = n/2
    
    // 分解数字
    a = floor(x / 10^m)
    b = x mod 10^m
    c = floor(y / 10^m)
    d = y mod 10^m
    
    // 三次递归乘法
    z1 = karatsuba(a, c)
    z3 = karatsuba(b, d)
    z2 = karatsuba(a+b, c+d) - z1 - z3
    
    // 合并结果
    return z1 * 10^(2*m) + z2 * 10^m + z3

时间复杂度分析

每次递归调用将问题规模减半，但需要进行三次递归调用，因此递归式为：

$T(n) = 3T(n/2) + O(n)$

根据主定理， $a=3$ , $b=2$ , $f(n)=O(n)$ ，有 $n^{\log_2 3} \approx n^{1.585} > n$ ，属于第一种情况，因此：

$T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$

这明显优于传统的 $O(n^2)$ 算法。

实例演示

计算 $123 \times 456$ ：

分解：
- $x = 123 = 1 \cdot 10^2 + 23$ ，所以 $a = 1$ , $b = 23$
- $y = 456 = 4 \cdot 10^2 + 56$ ，所以 $c = 4$ , $d = 56$
计算三个乘积：
- $z_1 = a \cdot c = 1 \cdot 4 = 4$
- $z_3 = b \cdot d = 23 \cdot 56 = 1288$
- $z_2 = (a+b)(c+d) - z_1 - z_3$
合并结果：
- $x \cdot y = 56088$

验证： $123 \times 456 = 56088$ ，结果正确。

优化与应用

阈值选择：当整数位数较少时，传统乘法可能更快。实践中通常设置一个阈值，低于该阈值时使用传统乘法。
内存优化：可以使用原地算法减少内存开销。
应用场景：
- 大数密码学（如RSA算法）
- 高精度计算
- 科学计算中的大数运算

分治算法的时间与空间复杂度对比表

算法名称	时间复杂度	空间复杂度	备注
二分搜索	$O(\log n)$	$O(1)$ （迭代）或 $O(\log n)$ （递归）	在有序数组中查找目标值
朴素分治矩阵乘法	$O(n^3)$	$O(\log n)$ （递归栈）	划分为子矩阵，8次递归
Strassen矩阵乘法	$O(n^{\log_2 7}) \approx O(n^{2.81})$	$O(n^{\log_2 7})$	减少递归次数到7次
大整数乘法（Karatsuba）	$O(n^{\log_2 3}) \approx O(n^{1.585})$	$O(n^{\log_2 3})$	使用分治减少乘法次数
最近点对问题	$O(n \log n)$	$O(n)$	平面中找出距离最小的两个点

随机化算法

随机化算法是一种在执行过程中引入随机性（如随机选择、随机划分等）的算法。它通过引入随机决策来改善算法的平均性能或简化实现方式，常用于解决最坏情况下的效率瓶颈问题。

特点：

依赖于随机数生成器。
可能产生不同的结果（取决于随机选择）。
在某些问题上比确定性算法更高效或更容易实现。

应用场景：

快速排序中的随机选主元（随机快速排序）
大整数素性测试（如 Miller-Rabin）
图论中的随机游走
哈希冲突处理、负载均衡等

Las Vegas 算法

Las Vegas 算法是一类总是返回正确结果的随机化算法，但其运行时间是随机的。

核心特征：

结果正确。
运行时间不确定，可能因随机选择而变长或变短。

示例：

随机快速排序：每次划分的基准值是随机选取的，虽然运行时间可能不同，但最终结果始终有序。
随机化哈希查找：在冲突处理中使用随机探测策略。

时间复杂度：

通常分析其期望运行时间，例如 $O(n \log n)$ 。

Monte Carlo 算法

Monte Carlo 算法是一类运行时间固定或有界的随机化算法，但它可能返回错误的结果，不过可以通过多次运行来降低出错概率。

核心特征：

运行时间可预测。
结果可能不正确，但错误概率可以控制。

示例：

Miller-Rabin 素性测试：用于判断一个大整数是否为素数，有一定的误判率，但可通过多轮测试将错误概率降到极低。
Freivalds 算法：用于验证矩阵乘积是否正确，通过随机向量近似判断，具有一定的错误概率。

时间复杂度：

通常是固定的，如 $O(n^2)$ 或 $O(1)$ 。

雇佣问题

雇佣问题是一个经典的算法问题，用于说明随机化方法的优势。

问题描述：

假设一家公司需要雇佣一名员工，有 $n$ 个应聘者按顺序前来面试。每面试完一个人后，公司必须立即决定是否雇佣。如果决定雇佣，则解雇之前雇佣的人（如果有）。目标是雇佣最优秀的应聘者，但面试顺序是预先确定的。

确定性算法分析：

贪心策略：每次遇到比当前雇员更优秀的应聘者就雇佣。
成本分析：
- 每次雇佣成本为 $c_h$
- 每次面试成本为 $c_i$
- 总成本 = 面试成本 + 雇佣成本 = $c_i \cdot n + c_h \cdot h$ ，其中 $h$ 是雇佣次数
最坏情况：如果应聘者按能力递增排序，则每个人都会被雇佣，总雇佣次数 $h = n$ ，总成本为 $c_i \cdot n + c_h \cdot n = (c_i + c_h) \cdot n$ 。

问题挑战：

在应聘者顺序固定的情况下，无法避免最坏情况。这就引出了随机化雇佣问题的思路。

随机化雇佣问题

随机化雇佣问题通过打乱应聘者的面试顺序来改善算法的期望性能。

算法思路：

将所有应聘者随机排序，打破可能的不利顺序。
按照随机顺序进行面试，仍采用贪心策略（雇佣更优秀的应聘者）。

期望成本分析：

指示器随机变量：
- 定义 $X_i$ 表示第 $i$ 个应聘者是否被雇佣（1表示雇佣，0表示不雇佣）。
- 雇佣总次数 $X = \sum_{i=1}^{n} X_i$ 。
概率分析：
- 应聘者 $i$ 被雇佣的条件是：他是前 $i$ 个应聘者中最优秀的。
- 由于随机排序，应聘者 $i$ 是前 $i$ 个人中最优秀的概率为 $\frac{1}{i}$ 。
- 因此 $E[X_i] = \frac{1}{i}$ 。
期望雇佣次数：
$E[X] = E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i] = H_n \approx \ln n$
其中 $H_n$ 是第 $n$ 个调和数，近似为 $\ln n$ 。
期望总成本：
$E[\text{C}] = c_i \cdot n + c_h \cdot E[X] \approx c_i \cdot n + c_h \cdot \ln n$

结论：

随机化将雇佣次数从最坏情况的 $O(n)$ 降低到期望 $O(\ln n)$ ，显著降低了总成本。

生成随机排列的两种方法

随机排列生成是许多随机化算法的基础，包括上述的随机化雇佣问题。以下介绍两种常用的生成方法。

方法一：随机排序法

这种方法基于排序算法，通过为每个元素分配一个随机优先级，然后按优先级排序。

算法步骤：

为数组 $A[1...n]$ 中的每个元素 $A[i]$ 分配一个随机优先级 $P[i]$ 。
根据优先级 $P$ 对数组 $A$ 进行排序。

伪代码：

RANDOM-SORT(A)
    n = A.length
    let P[1..n] be a new array
    for i = 1 to n
        P[i] = RANDOM()  // 生成[0,1)之间的随机数
    sort A according to the priorities in P
    return A

时间复杂度：

生成随机数： $O(n)$
排序： $O(n \log n)$
总时间复杂度： $O(n \log n)$

方法二：原地随机排列法（Fisher-Yates 洗牌算法）

这种方法更高效，直接在原数组上进行操作，不需要额外的排序步骤。

算法步骤：

从数组末尾开始，逐步向前处理。
对于位置 $i$ ，随机选择 $[1,i]$ 范围内的一个位置 $j$ 。
交换 $A[i]$ 和 $A[j]$ 。

伪代码：

RANDOMIZE-IN-PLACE(A)
    n = A.length
    for i = n downto 2
        j = RANDOM(1, i)  // 生成1到i之间的随机整数
        exchange A[i] with A[j]
    return A

正确性证明：

需要证明每个可能的排列出现的概率都是 $\frac{1}{n!}$ 。

归纳假设：在第 $i$ 次迭代开始时， $A[i+1...n]$ 的每个排列出现的概率都是 $\frac{1}{(n-i)!}$ 。
基础情况： $i=n$ ，显然成立。
归纳步骤：
- 第 $i$ 次迭代将 $A[j]$ 放到位置 $i$ ，概率为 $\frac{1}{i}$ 。
- 结合归纳假设， $A[i...n]$ 的每个排列出现的概率为 $\frac{1}{i} \cdot \frac{1}{(n-i)!} = \frac{1}{(n-(i-1))!}$ 。
结论：当 $i=1$ 时，整个数组 $A[1...n]$ 的每个排列出现的概率为 $\frac{1}{n!}$ 。

时间复杂度：

$O(n)$ ，明显优于第一种方法。

随机化快速排序

快速排序是一种经典的分治排序算法，其性能高度依赖于选择的枢轴（pivot）。随机化快速排序通过随机选择枢轴来避免最坏情况。

标准快速排序的问题：

最坏情况：当输入数组已经排序或接近排序时，如果总是选择第一个或最后一个元素作为枢轴，时间复杂度退化为 $O(n^2)$ 。
攻击可能性：如果算法的选择枢轴策略是确定的，可能被恶意构造的输入所攻击。

随机化快速排序算法：

核心思想：

随机选择枢轴，打破输入数据可能存在的不利模式。

算法步骤：

随机选择一个元素作为枢轴。
将数组划分为小于枢轴和大于枢轴的两部分。
递归地对两个子数组进行排序。

伪代码：

RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        q = RANDOMIZED-PARTITION(A, p, r)
        RANDOMIZED-QUICKSORT(A, p, q-1)
        RANDOMIZED-QUICKSORT(A, q+1, r)

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)  // 随机选择枢轴
    exchange A[r] with A[i]
    return PARTITION(A, p, r)  // 标准的划分过程

性能分析：

期望时间复杂度：
- 平均情况： $O(n \log n)$
- 最坏情况仍为 $O(n^2)$ ，但概率极低
优势：
- 对任何输入数据，期望性能都是 $O(n \log n)$
- 不易受到恶意构造的输入攻击
- 实现简单，只需在标准快速排序基础上做小改动
实际应用：
- 大多数实际实现的快速排序都采用随机化策略
- 通常与其他优化（如三数取中、小数组使用插入排序等）结合使用

随机化分析：

随机化快速排序的关键在于，通过随机选择枢轴，使得任何输入数据的期望运行时间都接近平均情况，而不是最坏情况。

具体来说，对于长度为 $n$ 的数组，随机选择枢轴将数组划分为比例为 $1:9$ 的两部分的概率是 $\frac{1}{5}$ 。这种"不太平衡"的划分仍然能保证 $O(n \log n)$ 的时间复杂度，因为递归树的高度仍然是 $O(\log n)$ 。

只有当连续多次都出现极度不平衡的划分（如 $99\%:1\%$ ）时，才会导致性能接近 $O(n^2)$ ，而这种情况的概率随着数组大小的增加而迅速减小。

Las Vegas 与 Monte Carlo 对比

特征	Las Vegas 算法	Monte Carlo 算法
结果是否正确	总是正确	可能错误
运行时间	不确定（随机）	固定或有界
是否可重复	可重复以提高效率	可重复以降低错误概率
典型应用	排序、搜索、哈希冲突处理	素性测试、矩阵乘法验证、模拟实验
优点	正确性强	效率高，适用于实时系统
缺点	最坏情况下可能耗时过长	存在一定错误概率

使用指纹法进行串相等性测试

Las Vegas的一个典型实例就是随机化快速排序；而 Monte Carlo 算法我们也有个实例：

Monte Carlo 算法是一种运行时间固定或有界、但可能返回错误结果的随机化算法。其核心思想是：

通过引入随机性，以概率方式近似解决问题。
错误的概率可以通过重复执行来降低。

在某些情况下，允许一定小概率出错可以极大地提高效率，例如在网络传输中验证文件一致性、数据库同步等场景。

给定两个长度为 $n$ 的字符串 $A$ 和 $B$ ，我们想判断它们是否完全相等。

如果直接逐字符比较，时间复杂度为 $O(n)$ 。但如果这两个字符串分布在不同的节点上（如网络通信），传输整个字符串进行比较代价很高。

于是我们希望：

只传输少量信息（指纹）
以高概率正确判断字符串是否相等

这就是指纹法的应用场景。

指纹法的基本思路（Fingerprinting）

将字符串映射成一个短整数（指纹），然后仅比较指纹即可判断字符串是否相等。

若指纹相同，则认为字符串相等；否则肯定不同。

虽然存在极小概率"碰撞"（即不同字符串指纹相同），但这种错误概率可以通过参数控制到极低。

具体实现步骤（Monte Carlo 风格）

选择一个大素数 $p$ （比如从某个范围内随机选取）。
定义指纹函数： F(A) = (A_1 \cdot b^{n-1} + A_2 \cdot b^{n-2} + \cdots + A_n) \mod p其中 $b$ 是一个固定的基数（如 256 或 10）， $A_i$ 是字符的 ASCII 值。
计算字符串 $A$ 和 $B$ 的指纹值 $F(A), F(B)$
比较指纹值：
- 如果 $F(A) \neq F(B)$ ，则 $A \neq B$ （确定）
- 如果 $F(A) = F(B)$ ，则认为 $A = B$ （有一定错误概率）

错误概率分析

设：

所有字符串长度为 $n$
字符集大小为 $|\Sigma|$
随机选一个素数 $p$ 在 $[2, P]$ 范围内

那么：

不同字符串产生相同指纹的概率约为 $\frac{1}{p}$

只要选择足够大的 $p$ （如 $p \approx 10^9$ ），错误概率就非常小（约十亿分之一）。

简而言之就是把大数除以一个素数变成一个比较小的数再比较。

选择与统计算法

在计算机科学中，选择与统计算法用于从一个无序或部分有序的序列中找出特定顺序统计量（order statistic），例如：

最小值（first order statistic）
最大值（maximum）
第 k 小元素（k-th smallest element）

这类问题广泛应用于数据库查询、数据挖掘、算法优化等领域。

常见问题包括：

找出数组中的最大值、最小值
同时找出最大值和最小值
在线性时间内找到第 k 小元素（如快速选择算法）

求序列中的最大值和最小值

问题描述：

给定一个包含 $n$ 个不同元素的数组 $A[1..n]$ ，要求找出其中的最大值和最小值。

方法一：朴素比较法

逐个比较每个元素，分别更新当前最大值和最小值。

时间复杂度：

比较次数： $2(n - 1)$

空间复杂度：

$O(1)$ ，仅需存储 max 和 min 变量

方法二：成对比较法（优化）

将数组中的元素两两配对，先比较每一对，再分别与当前最大值和最小值比较。

步骤：

成对比较相邻元素。
较大的那个与当前最大值比较。
较小的那个与当前最小值比较。

时间复杂度：

比较次数：约 $\frac{3}{2}n$

示例代码（Python）：

python

def find_min_max(A):
    n = len(A)
    if n % 2 == 0:
        min_val = min(A[0], A[1])
        max_val = max(A[0], A[1])
        i = 2
    else:
        min_val = max_val = A[0]
        i = 1

    while i < n:
        if A[i] < A[i + 1]:
            min_val = min(min_val, A[i])
            max_val = max(max_val, A[i + 1])
        else:
            min_val = min(min_val, A[i + 1])
            max_val = max(max_val, A[i])
        i += 2

    return min_val, max_val

问题二：选择第 k 小元素

问题描述：

给定一个大小为 $n$ 的数组 $A$ 和一个整数 $k$ （ $1 \leq k \leq n$ ），找出数组中第 $k$ 小的元素。

方法一：排序后直接取（确定性）

思路：

对数组进行排序（如归并排序、快速排序）
返回排序后数组的第 $k-1$ 项

时间复杂度：

$O(n \log n)$

方法二：快速选择算法（Quickselect）——期望线性时间

思路：

类似于快速排序的分治策略
随机选取一个主元（pivot）
分区后判断 pivot 是否是第 k 小元素
若不是，则递归查找左子数组或右子数组

时间复杂度：

平均情况： $O(n)$
最坏情况： $O(n^2)$

Python 示例：

python

import random

def partition(A, left, right):
    pivot_idx = random.randint(left, right)
    A[pivot_idx], A[right] = A[right], A[pivot_idx]
    pivot = A[right]
    i = left
    for j in range(left, right):
        if A[j] <= pivot:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[i], A[right] = A[right], A[i]
    return i

def quickselect(A, left, right, k):
    if left == right:
        return A[left]

    pivot_idx = partition(A, left, right)

    if k == pivot_idx:
        return A[k]
    elif k < pivot_idx:
        return quickselect(A, left, pivot_idx - 1, k)
    else:
        return quickselect(A, pivot_idx + 1, right, k)

方法三：BFPRT 算法（最坏情况线性时间的选择算法）

核心思想：

使用"中位数的中位数"方法来选择 pivot
保证最坏情况下也能达到 $O(n)$ 时间复杂度

步骤简述：

将数组划分为若干个 5 元素小组。
对每个小组排序，取出中位数。
递归求这些中位数的中位数作为 pivot。
使用该 pivot 进行分区，并根据位置决定递归方向。

时间复杂度：

最坏情况： $O(n)$

总结对比表

问题	方法	时间复杂度	是否随机	备注
最大/最小值	成对比较法	$O(n)$	❌ 否	比较次数约 $\frac{3}{2}n$
第 k 小元素	排序法	$O(n \log n)$	❌ 否	简单但效率低
第 k 小元素	快速选择（Quickselect）	平均 $O(n)$ ，最坏 $O(n^2)$	✅ 是	期望线性时间
第 k 小元素	BFPRT 算法	$O(n)$	❌ 否	最坏情况线性时间

当然可以。下面是对**动态规划（Dynamic Programming, DP）**的简要介绍，并对以下三个经典问题进行详细分析：

装配线调度问题
矩阵链相乘问题
最长公共子序列问题

每个问题都包括：

问题描述
动态规划建模思路
状态转移方程
时间复杂度和空间复杂度分析

一、动态规划简介

什么是动态规划？

动态规划是一种用于解决具有重叠子问题和最优子结构性质的问题的算法设计方法。

它通过将原问题分解为更小的子问题，自底向上求解并保存中间结果，从而避免重复计算，提高效率。

动态规划的核心思想：

最优子结构：原问题的最优解包含子问题的最优解。
重叠子问题：在递归求解过程中，子问题会被多次重复调用。
状态表示与转移：定义合适的状态变量，并建立状态之间的递推关系。
记忆化或表格法：保存已计算的结果以避免重复计算。

应用场景：

最短路径问题（如Floyd-Warshall）
资源分配问题
字符串匹配问题（如LCS）
组合优化问题（如背包问题）

装配线调度问题（Assembly-Line Scheduling）

问题描述：

某汽车工厂有两条装配线，每条装配线有 $n$ 个装配站。从第 $i$ 个站到下一站的时间是固定的，也可以跨线跳转，但需要额外时间。目标是从起点到终点选择一条耗时最短的路径。

输入参数：

$a_{i,j}$ ：第 $i$ 条装配线第 $j$ 个站所需时间
$t_{i,j}$ ：从第 $i$ 条线第 $j$ 个站跳转到另一条线的花费
$e_i$ ：进入第 $i$ 条线的初始时间
$x_i$ ：离开第 $i$ 条线的最终时间

动态规划建模：

设 $f[i][j]$ 表示到达第 $i$ 条线第 $j$ 个站所需的最短时间。

状态转移方程：

f[1][j] = \min(f[1][j-1] + a_{1,j},\ f[2][j-1] + t_{2,j-1} + a_{1,j}) \\ f[2][j] = \min(f[2][j-1] + a_{2,j},\ f[1][j-1] + t_{1,j-1} + a_{2,j})

初始条件：

$f[1][1] = e_1 + a_{1,1}, f[2][1] = e_2 + a_{2,1}$

最终答案：

$\min(f[1][n] + x_1,\ f[2][n] + x_2)$

时间复杂度：

$O(n)$

空间复杂度：

$O(n)$ 或可优化至 $O(1)$ （只保留前一层）

矩阵链相乘问题（Matrix Chain Multiplication）

问题描述：

给定一个矩阵链 $A_1A_2...A_n$ ，其中 $A_i$ 的维度为 $p_{i-1} \times p_i$ 。求一种加括号方式使得矩阵乘积所需的标量乘法次数最少。

动态规划建模：

设 $m[i][j]$ 表示将 $A_iA_{i+1}...A_j$ 相乘所需的最小乘法次数。

状态转移方程：

$m[i][j] = \min_{i \leq k < j} (m[i][k] + m[k+1][j] + p_{i-1}p_kp_j)$

初始条件：

m[i][i] = 0 \quad (\text{单个矩阵无需乘法})

构造最优解（可选）：

可用辅助数组 $s[i][j]$ 记录分割点 $k$ ，便于构造括号表达式。

时间复杂度：

$O(n^3)$

空间复杂度：

$O(n^2)$

最长公共子序列问题（Longest Common Subsequence, LCS）

问题描述：

给定两个字符串 $X[1..m]$ 和 $Y[1..n]$ ，找出它们的最长公共子序列（不一定是连续的）。

动态规划建模：

设 $c[i][j]$ 表示 $X[1..i]$ 和 $Y[1..j]$ 的 LCS 长度。

状态转移方程：

$c[i][j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ c[i-1][j-1] + 1 & \text{if } X[i] = Y[j] \\ \max(c[i-1][j], c[i][j-1]) & \text{if } X[i] \ne Y[j] \end{cases}$

构造实际子序列（可选）：

可用回溯法从 $c[m][n]$ 往前构造出具体的 LCS。

时间复杂度：

$O(mn)$

空间复杂度：

$O(mn)$ ，也可优化至 $O(\min(m,n))$ 使用滚动数组

总结对比：

问题	状态定义	状态转移方程	时间复杂度	空间复杂度
装配线调度	$f[i][j]$ ：到达第 $i$ 条线第 $j$ 个站的最短时间	分别考虑同线和跳线情况	$O(n)$	$O(n)$
矩阵链相乘	$m[i][j]$ ： $A_i...A_j$ 的最小乘法次数	枚举分割点 $k$	$O(n^3)$	$O(n^2)$
最长公共子序列	$c[i][j]$ ： $X[1..i]$ 和 $Y[1..j]$ 的 LCS 长度	比较字符是否相等	$O(mn)$	$O(mn)$

贪心算法

贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即局部最优）的选择，从而希望导致结果是全局最优的算法策略。

贪心算法的基本思想

贪心算法的核心思想非常简单：

将问题分解为一系列子问题
对每个子问题做出局部最优的选择（贪心选择）
希望这些局部最优选择能导致全局最优解

虽然贪心算法看似简单，但要正确使用需要满足两个关键性质：

1. 贪心选择性质

问题的整体最优解可以通过一系列局部最优的选择来达到。换句话说，做出的每个贪心选择最终能导致全局最优解。

2. 最优子结构性质

问题的最优解包含其子问题的最优解。这意味着做出一个选择后，只需要解决剩下的一个子问题。

贪心算法与动态规划的区别

特征	贪心算法	动态规划
最优性	不一定能得到全局最优解	总是能得到全局最优解
效率	通常更高效	通常需要更多时间和空间
决策过程	一旦做出选择，不再更改	考虑所有可能的选择，然后选择最优的
适用条件	贪心选择性质和最优子结构	只需要最优子结构

作业选择问题

问题描述

有 $n$ 个作业，每个作业 $i$ 有一个开始时间 $s_i$ 和结束时间 $f_i$ 。两个作业如果时间重叠，则不能同时处理。目标是选择最大数量的互不冲突的作业。

贪心策略

按照作业的结束时间从早到晚排序，然后每次选择当前不冲突的结束最早的作业。

算法步骤

将所有作业按照结束时间 $f_i$ 排序
选择第一个作业（结束最早的）
遍历排序后的作业，如果当前作业的开始时间不早于最近选择的作业的结束时间，则选择该作业

算法正确性证明

我们可以通过交换论证来证明贪心选择的正确性：

假设存在一个包含作业 $j$ 的最优解 $A$ ，而 $j$ 不是结束最早的作业。设作业 $i$ 是结束最早的作业。

我们可以构造一个新解 $A'$ ，用作业 $i$ 替换作业 $j$ 。由于 $i$ 的结束时间早于 $j$ ，因此替换后不会产生新的冲突。所以 $A'$ 也是一个最优解。

通过这种方式，我们可以不断调整解，最终得到一个包含结束最早的作业的最优解。这证明了选择结束最早的作业是安全的。

示例

作业列表：[(1,3), (2,5), (4,7), (6,9), (5,8)]，表示 (开始时间, 结束时间)

排序后：[(1,3), (2,5), (4,7), (5,8), (6,9)]
选择 (1,3)
选择 (4,7)
选择 (6,9) 或 (8,10)

最终选择的作业为 3 个。

时间复杂度

排序： $O(n \log n)$
贪心选择： $O(n)$
总体： $O(n \log n)$

哈夫曼编码

问题描述

给定一组字符及其出现频率，为每个字符设计一个变长前缀码，使得编码后的总长度最小。前缀码是指没有任何码字是另一个码字的前缀的编码方式，这保证了解码的唯一性。

贪心策略

反复合并两个频率最低的节点，构建一棵二叉树，最终树的带权路径长度最小。

算法步骤

将所有字符及其频率作为单节点放入优先队列
每次从队列中取出两个频率最小的节点，创建一个新节点作为它们的父节点，新节点的频率是两个子节点频率之和
将新节点放回队列
重复步骤 2-3，直到队列中只剩一个节点，这个节点就是哈夫曼树的根节点
从根到叶子的路径决定了每个字符的编码（左边为 0，右边为 1）

正确性证明

对于哈夫曼编码的贪心策略，我们可以证明：

引理：在最优编码树中，频率最低的两个字符一定在树的最底层，且它们是兄弟节点。
基于此引理，合并频率最低的两个节点是安全的贪心选择。

证明利用了交换论证和剪切粘贴论证，显示如果最优解不符合这个特性，我们总能通过调整得到一个更优的解，从而导致矛盾。

示例

字符及频率：A(5), B(9), C(12), D(13), E(16), F(45)

构建过程：

初始优先队列：[A(5), B(9), C(12), D(13), E(16), F(45)]
取出并合并最小的两个节点 A(5) 和 B(9)，得到新节点 AB(14)
- 队列变为：[C(12), D(13), AB(14), E(16), F(45)]
取出并合并最小的两个节点 C(12) 和 D(13)，得到新节点 CD(25)
- 队列变为：[AB(14), E(16), CD(25), F(45)]
取出并合并最小的两个节点 AB(14) 和 E(16)，得到新节点 ABE(30)
- 队列变为：[CD(25), ABE(30), F(45)]
取出并合并最小的两个节点 CD(25) 和 ABE(30)，得到新节点 CDABE(55)
- 队列变为：[F(45), CDABE(55)]
取出并合并最小的两个节点 F(45) 和 CDABE(55)，得到根节点 FCDABE(100)

最终哈夫曼树构建完成。通过从根到叶子的路径，左分支为0，右分支为1，可以得到编码：

A: 0010
B: 0011
C: 100
D: 101
E: 010
F: 11

这种编码方式保证了频率高的字符（如F）编码较短，频率低的字符（如A）编码较长，从而使得编码总长度最小。

时间复杂度

建立优先队列： $O(n)$
合并操作：每次需要 $O(\log n)$ ，共进行 $n-1$ 次
总体： $O(n \log n)$

背包问题

背包问题是一类经典的组合优化问题。有以下几种常见变种：

1. 0-1 背包问题

每个物品只能选择放或不放，不能部分选择。这个问题通常使用动态规划而非贪心算法解决，因为贪心策略在这种情况下不能保证最优解。

2. 分数背包问题

物品可以部分选择，即可以拿走物品的一部分。这个问题可以用贪心算法解决。

问题描述

有 $n$ 个物品，每个物品有重量 $w_i$ 和价值 $v_i$ 。背包容量为 $W$ 。可以拿走物品的一部分，目标是使背包中物品的总价值最大。

贪心策略

按照物品的价值密度（价值/重量）从高到低排序，然后依次尽可能多地装入背包。

算法步骤

计算每个物品的价值密度 $v_i/w_i$
按照价值密度从高到低排序
依次将物品装入背包，直到背包装满或物品用完
如果当前物品不能完全装入背包，则装入该物品的一部分，使背包恰好装满

正确性证明

假设最优解不是按照价值密度排序的，那么存在两个物品 $i$ 和 $j$ ，满足 $v_i/w_i > v_j/w_j$ ，但在最优解中物品 $j$ 的选择比例高于物品 $i$ 。

我们可以通过减少物品 $j$ 的选择，增加物品 $i$ 的选择，在保持总重量不变的情况下增加总价值，这与最优解的假设矛盾。因此，按照价值密度排序是正确的贪心策略。

示例

物品：[(10,60), (20,100), (30,120)]，表示 (重量, 价值)

价值密度：[6, 5, 4]

背包容量：50

贪心选择：

选择物品 1，剩余容量 40
选择物品 2，剩余容量 20
选择 2/3 的物品 3，背包装满

总价值：60 + 100 + 120 * (2/3) = 240

时间复杂度

计算价值密度： $O(n)$
排序： $O(n \log n)$
贪心选择： $O(n)$
总体： $O(n \log n)$

贪心算法的应用场景

贪心算法适用于以下场景：

最优子结构：问题的最优解包含子问题的最优解
贪心选择性质：局部最优选择能导致全局最优解
无后效性：之前的选择不会影响后续的子问题

常见的应用：

最小生成树：Kruskal 算法和 Prim 算法
单源最短路径：Dijkstra 算法
集合覆盖问题：近似算法
霍夫曼编码：数据压缩
作业调度问题：最小化完成时间

贪心算法的限制

贪心算法虽然高效，但也有明显的局限性：

不保证全局最优：在许多问题中，贪心选择无法得到全局最优解
适用性有限：只有特定问题满足贪心选择性质
证明困难：证明贪心算法的正确性通常比较复杂

因此，在应用贪心算法前，需要仔细分析问题是否满足贪心算法的适用条件。如果不确定，可能需要考虑其他算法策略，如动态规划或回溯法。

图论

图是一种由节点（顶点）和边组成的数据结构，用于表示元素之间的关系。图论是研究图的数学理论，在计算机科学中有广泛的应用。

图的基础

图的定义与术语

图 $G = (V, E)$ 由以下元素组成：

顶点集 $V$ ：图中所有节点的集合
边集 $E$ ：连接顶点的边的集合，可表示为顶点对 $(u, v)$

重要概念：

相邻顶点：由边直接连接的两个顶点
度：与某顶点相连的边的数量
路径：从一个顶点到另一个顶点经过的边的序列
环：起点和终点相同的路径
连通图：任意两个顶点之间都存在路径的图
连通分量：图中的极大连通子图

图的分类

无向图：边没有方向， $(u, v)$ 和 $(v, u)$ 表示同一条边
有向图：边有方向，从 $u$ 到 $v$ 的边表示为 $(u, v)$ 或 $u \rightarrow v$
加权图：每条边都有一个权值，表示距离、成本等
无权图：边没有权值，或所有边的权值相同
稠密图：边的数量接近于 $|V|^2$ 的图
稀疏图：边的数量远小于 $|V|^2$ 的图
完全图：任意两个顶点之间都有边的图
二分图：顶点可以分为两个互不相交的集合，每条边连接的两个顶点分别来自这两个集合

图的表示方法

邻接矩阵：
- 使用 $|V| \times |V|$ 的矩阵 $A$
- 若 $u$ 和 $v$ 之间有边，则 $A[u][v] = 1$ （或权值），否则 $A[u][v] = 0$
- 优点：查询边是否存在的时间为 $O(1)$
- 缺点：空间复杂度为 $O(|V|^2)$ ，对于稀疏图不高效
邻接表：
- 对每个顶点 $u$ ，存储与其相邻的顶点列表
- 优点：空间复杂度为 $O(|V| + |E|)$ ，适合稀疏图
- 缺点：查询边是否存在的时间为 $O(d)$ ，其中 $d$ 是顶点的度

选择表示方法的准则：

稠密图或需要快速查询边时，选择邻接矩阵
稀疏图或需要遍历所有边时，选择邻接表

图的遍历

图的遍历是指访问图中所有顶点的过程，主要有两种方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索 (DFS)

DFS 是一种通过递归或栈实现的图遍历算法，其特点是尽可能深地探索图的分支。

算法步骤：

选择一个起始顶点，标记为已访问
递归地访问与当前顶点相邻的未访问顶点
如果当前顶点的所有相邻顶点都已访问，则回溯到上一个顶点
重复步骤 2-3，直到所有顶点都已访问

实现（递归）：

python

def dfs(graph, vertex, visited):
    visited[vertex] = True
    print(vertex, end=' ')  # 处理当前顶点
    
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def dfs_traversal(graph, start_vertex):
    visited = [False] * len(graph)
    dfs(graph, start_vertex, visited)
    
    # 处理非连通图的情况
    for v in range(len(graph)):
        if not visited[v]:
            dfs(graph, v, visited)

实现（栈）：

python

def dfs_iterative(graph, start_vertex):
    visited = [False] * len(graph)
    stack = [start_vertex]
    
    while stack:
        vertex = stack.pop()
        
        if not visited[vertex]:
            visited[vertex] = True
            print(vertex, end=' ')  # 处理当前顶点
            
            # 注意这里要倒序加入，以保持与递归版本相同的访问顺序
            for neighbor in reversed(graph[vertex]):
                if not visited[neighbor]:
                    stack.append(neighbor)

时间复杂度：

邻接表表示： $O(|V| + |E|)$
邻接矩阵表示： $O(|V|^2)$

应用：

寻找图中的连通分量
检测环
拓扑排序
寻找路径
求解迷宫问题

广度优先搜索 (BFS)

BFS 是一种通过队列实现的图遍历算法，其特点是先访问距离起始顶点近的顶点，再访问距离远的顶点。

算法步骤：

选择一个起始顶点，标记为已访问，并将其加入队列
从队列中取出一个顶点，访问其所有未访问的相邻顶点，标记它们为已访问，并加入队列
重复步骤 2，直到队列为空

实现：

python

from collections import deque

def bfs(graph, start_vertex):
    visited = [False] * len(graph)
    queue = deque([start_vertex])
    visited[start_vertex] = True
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')  # 处理当前顶点
        
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
                
    # 处理非连通图的情况
    for v in range(len(graph)):
        if not visited[v]:
            queue.append(v)
            visited[v] = True
            while queue:
                # 重复上述过程
                vertex = queue.popleft()
                print(vertex, end=' ')
                
                for neighbor in graph[vertex]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)

时间复杂度：

邻接表表示： $O(|V| + |E|)$
邻接矩阵表示： $O(|V|^2)$

应用：

寻找最短路径（无权图）
寻找距离起始顶点特定距离的所有顶点
寻找图中的层次结构
寻找网络中的所有节点
解决特定问题（如最小生成树的 Prim 算法）

DFS 与 BFS 的比较

特性	DFS	BFS
实现方式	递归或栈	队列
空间复杂度	$O(h)$ ， $h$ 是图的高度	$O(w)$ ， $w$ 是图的宽度
适用场景	探索所有可能路径寻找连通分量检测环	寻找最短路径层序遍历寻找特定距离的顶点
遍历顺序	深度优先	广度优先
完备性	可能不完备（在无限图中）	完备（总能找到解，如果存在）

拓扑排序

拓扑排序是对有向无环图 (DAG) 的顶点进行排序，使得对于图中的每条有向边 $(u, v)$ ，顶点 $u$ 在排序中都出现在顶点 $v$ 之前。

应用场景

任务调度：确定任务的执行顺序
编译依赖：确定编译顺序
课程安排：确定先修课程和后续课程的顺序
事件调度：确定事件的时间先后关系

算法实现

拓扑排序有两种常见的实现方式：Kahn 算法（基于 BFS）和 DFS 算法。

Kahn 算法（BFS 实现）

算法步骤：

计算图中每个顶点的入度
将所有入度为 0 的顶点加入队列
从队列中取出一个顶点，将其加入拓扑排序的结果中
减少该顶点的所有邻接顶点的入度，如果减少后入度为 0，则将该邻接顶点加入队列
重复步骤 3-4，直到队列为空

实现：

python

from collections import deque

def topological_sort_bfs(graph):
    in_degree = [0] * len(graph)
    
    # 计算每个顶点的入度
    for u in range(len(graph)):
        for v in graph[u]:
            in_degree[v] += 1
    
    # 将所有入度为 0 的顶点加入队列
    queue = deque()
    for u in range(len(graph)):
        if in_degree[u] == 0:
            queue.append(u)
    
    # 拓扑排序结果
    topo_order = []
    
    # BFS
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 检查是否存在环
    if len(topo_order) != len(graph):
        return None  # 存在环，无法进行拓扑排序
    
    return topo_order

DFS 实现

算法步骤：

对图进行 DFS 遍历
在 DFS 的过程中，当一个顶点的所有邻接顶点都已访问完成后，将该顶点加入结果
最后，将结果反转

实现：

python

def topological_sort_dfs(graph):
    visited = [False] * len(graph)
    temp = [False] * len(graph)  # 用于检测环
    topo_order = []
    
    def dfs(u):
        if temp[u]:  # 存在环
            return False
        if visited[u]:
            return True
        
        temp[u] = True
        
        for v in graph[u]:
            if not dfs(v):
                return False
        
        temp[u] = False
        visited[u] = True
        topo_order.append(u)
        return True
    
    for u in range(len(graph)):
        if not visited[u]:
            if not dfs(u):
                return None  # 存在环，无法进行拓扑排序
    
    topo_order.reverse()  # 反转结果
    return topo_order

时间复杂度

Kahn 算法： $O(|V| + |E|)$
DFS 实现： $O(|V| + |E|)$

注意事项

拓扑排序只适用于有向无环图 (DAG)
如果图中存在环，则无法进行拓扑排序
一个图可能有多个有效的拓扑排序结果

强连通分量

强连通分量（Strongly Connected Component, SCC）是有向图中的一个子图，其中任意两个顶点之间都存在路径。

定义与性质

强连通图：任意两个顶点之间都存在路径的有向图。
强连通分量：有向图中的极大强连通子图。
性质：一个有向图可以分解为多个强连通分量，这些强连通分量之间形成一个有向无环图。

Kosaraju 算法

Kosaraju 算法是一种基于两次 DFS 的强连通分量算法。

算法步骤：

对原图进行 DFS，记录顶点的完成时间（或使用栈记录顶点的访问顺序）
构造原图的转置图（将所有边的方向反转）
按照第一步中顶点完成时间的逆序，对转置图进行 DFS
第二次 DFS 中，每次 DFS 遍历到的顶点集合就是一个强连通分量

实现：

python

def kosaraju(graph):
    n = len(graph)
    visited = [False] * n
    stack = []
    
    # 第一次 DFS，记录顶点的完成顺序
    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs1(v)
        stack.append(u)
    
    for u in range(n):
        if not visited[u]:
            dfs1(u)
    
    # 构造转置图
    transpose = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            transpose[v].append(u)
    
    # 第二次 DFS，寻找强连通分量
    visited = [False] * n
    scc = []
    
    def dfs2(u, component):
        visited[u] = True
        component.append(u)
        for v in transpose[u]:
            if not visited[v]:
                dfs2(v, component)
    
    while stack:
        u = stack.pop()
        if not visited[u]:
            component = []
            dfs2(u, component)
            scc.append(component)
    
    return scc

Tarjan 算法

Tarjan 算法是一种基于单次 DFS 的强连通分量算法，它利用了低链值（low-link value）的概念。

算法步骤：

对图进行 DFS，为每个顶点分配一个唯一的索引（发现时间）
同时计算每个顶点的低链值，即从该顶点出发通过树边和最多一条回边可以到达的最小索引
当一个顶点的索引等于其低链值时，该顶点是强连通分量的根
使用栈来收集当前 DFS 树中的顶点，以便在找到强连通分量时将其弹出

实现：

python

def tarjan(graph):
    n = len(graph)
    index_counter = [0]
    index = [-1] * n  # -1 表示未访问
    lowlink = [0] * n
    onstack = [False] * n
    stack = []
    scc = []
    
    def strongconnect(u):
        index[u] = index_counter[0]
        lowlink[u] = index_counter[0]
        index_counter[0] += 1
        stack.append(u)
        onstack[u] = True
        
        for v in graph[u]:
            if index[v] == -1:  # 邻接顶点未访问
                strongconnect(v)
                lowlink[u] = min(lowlink[u], lowlink[v])
            elif onstack[v]:  # 邻接顶点在栈中，形成环
                lowlink[u] = min(lowlink[u], index[v])
        
        # 如果 u 是强连通分量的根
        if lowlink[u] == index[u]:
            component = []
            while True:
                v = stack.pop()
                onstack[v] = False
                component.append(v)
                if v == u:
                    break
            scc.append(component)
    
    for u in range(n):
        if index[u] == -1:
            strongconnect(u)
    
    return scc

时间复杂度

Kosaraju 算法： $O(|V| + |E|)$
Tarjan 算法： $O(|V| + |E|)$

虽然两种算法的渐近时间复杂度相同，但 Tarjan 算法通常更高效，因为它只需要一次 DFS。

应用

社交网络分析：识别紧密相连的社区
电路分析：识别逻辑电路中的循环
计算机网络：分析网络拓扑结构
程序分析：识别程序中的循环依赖

最小生成树

最小生成树（Minimum Spanning Tree, MST）是连通加权无向图中一棵权值和最小的生成树。

基本概念

生成树：包含图中所有顶点的一棵树（无环连通子图）
最小生成树：所有可能的生成树中，边权之和最小的那棵
性质：
- MST 包含 $|V|-1$ 条边
- MST 是唯一的，当且仅当图中所有边的权值都不相同
- MST 满足最小权值原则：对于图中的任意切分，MST 使用了跨越该切分的最小权边

贪心策略

最小生成树算法通常基于贪心策略，有两种经典算法：Kruskal 算法和 Prim 算法。

Kruskal 算法

Kruskal 算法基于边的贪心策略，按照边权从小到大的顺序，依次添加不形成环的边。

算法步骤：

将图中所有边按权值从小到大排序
初始化 MST 为空集
按顺序考察每条边：如果添加当前边不会在 MST 中形成环，则将其添加到 MST 中
当 MST 中的边数达到 $|V|-1$ 时，算法结束

环检测：通常使用并查集（Disjoint Set）来高效检测环的形成。

实现：

python

def kruskal(graph, n):
    # 构建边列表
    edges = []
    for u in range(n):
        for v, weight in graph[u]:
            if u < v:  # 避免重复边
                edges.append((weight, u, v))
    
    # 按权值排序
    edges.sort()
    
    # 初始化并查集
    parent = list(range(n))
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        parent[find(x)] = find(y)
    
    # Kruskal 算法
    mst = []
    total_weight = 0
    
    for weight, u, v in edges:
        if find(u) != find(v):  # 不形成环
            union(u, v)
            mst.append((u, v, weight))
            total_weight += weight
            
            if len(mst) == n - 1:  # MST 已完成
                break
    
    return mst, total_weight

时间复杂度：

排序： $O(|E| \log |E|)$
并查集操作： $O(|E| \log |V|)$
总体： $O(|E| \log |E|)$ 或 $O(|E| \log |V|)$ ，因为 $|E| \leq |V|^2$ ，所以 $\log |E| \leq 2\log |V|$

适用场景：

稀疏图（边数远小于 $|V|^2$ ）
边按权值顺序处理的场景

Prim 算法

Prim 算法基于顶点的贪心策略，从一个起始顶点开始，逐步将与当前树相连的最小权边加入树中。

算法步骤：

选择一个起始顶点，将其加入 MST
初始化一个优先队列，包含所有与当前 MST 中顶点相邻的边
每次从优先队列中取出权值最小的边，如果该边连接的顶点尚未在 MST 中，则将边和顶点加入 MST
更新优先队列，加入与新顶点相邻的边
重复步骤 3-4，直到 MST 包含所有顶点

实现：

python

import heapq

def prim(graph, n, start=0):
    # 初始化
    visited = [False] * n
    mst = []
    total_weight = 0
    
    # 优先队列，存储 (权值, 顶点, 父顶点)
    pq = [(0, start, -1)]  # 初始顶点的权值为 0，父顶点为 -1
    
    while pq:
        weight, u, parent = heapq.heappop(pq)
        
        if visited[u]:
            continue
        
        visited[u] = True
        
        if parent != -1:  # 非起始顶点
            mst.append((parent, u, weight))
            total_weight += weight
        
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (w, v, u))
    
    return mst, total_weight

时间复杂度：

使用二叉堆： $O(|E| \log |V|)$
使用斐波那契堆： $O(|E| + |V| \log |V|)$

适用场景：

稠密图（边数接近 $|V|^2$ ）
需要从特定顶点开始构建 MST 的场景

Kruskal 与 Prim 比较

特性	Kruskal	Prim
基本策略	按边权排序，选择不构成环的边	从一个顶点开始，逐步扩展
数据结构	并查集	优先队列
适用图类型	稀疏图	稠密图
时间复杂度	$O(	E
实现难度	中等	中等
适用场景	边按权值排序的场景	从特定顶点开始的场景

单源最短路径问题

单源最短路径问题是指，给定一个带权图和一个源顶点，求源顶点到图中所有其他顶点的最短路径。

Bellman-Ford 算法

Bellman-Ford 算法可以处理带有负权边的图，能够检测负权环。

算法步骤：

初始化：源顶点到自身的距离为 0，到其他顶点的距离为无穷大
进行 $|V|-1$ $∣ V ∣ - 1$ 次迭代，每次迭代对图中的每条边 $(u, v)$ $(u, v)$ 进行松弛操作：
- 如果 $dist[u] + w(u, v) < dist[v]$ ，则更新 $dist[v] = dist[u] + w(u, v)$
再进行一次迭代，如果仍有边可以松弛，则图中存在负权环

松弛操作：尝试通过一个中间顶点来缩短两点间的距离。

实现：

python

def bellman_ford(graph, n, source):
    # 初始化距离
    dist = [float('inf')] * n
    dist[source] = 0
    
    # 前驱节点，用于重建路径
    predecessor = [None] * n
    
    # 主循环，进行 |V|-1 次迭代
    for _ in range(n - 1):
        for u in range(n):
            for v, weight in graph[u]:
                if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    predecessor[v] = u
    
    # 检测负权环
    for u in range(n):
        for v, weight in graph[u]:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                return None, None  # 存在负权环
    
    return dist, predecessor

时间复杂度： $O(|V| \cdot |E|)$

适用场景：

图中可能存在负权边
需要检测负权环
图比较稀疏

有向无环图 (DAG) 中的单源最短路径

在 DAG 中，可以使用拓扑排序来简化最短路径的计算。

算法步骤：

对 DAG 进行拓扑排序
按拓扑排序的顺序处理每个顶点，对其所有出边进行松弛操作

实现：

python

def dag_shortest_path(graph, n, source):
    # 拓扑排序
    def topological_sort():
        visited = [False] * n
        topo_order = []
        
        def dfs(u):
            visited[u] = True
            for v, _ in graph[u]:
                if not visited[v]:
                    dfs(v)
            topo_order.append(u)
        
        for u in range(n):
            if not visited[u]:
                dfs(u)
        
        topo_order.reverse()
        return topo_order
    
    # 获取拓扑排序
    topo_order = topological_sort()
    
    # 初始化距离
    dist = [float('inf')] * n
    dist[source] = 0
    
    # 前驱节点，用于重建路径
    predecessor = [None] * n
    
    # 按拓扑顺序处理每个顶点
    for u in topo_order:
        if dist[u] != float('inf'):
            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    predecessor[v] = u
    
    return dist, predecessor

时间复杂度： $O(|V| + |E|)$

适用场景：

图是有向无环图
需要高效计算单源最短路径

Dijkstra 算法

Dijkstra 算法用于求解非负权图的单源最短路径问题，是一种贪心算法。

算法步骤：

初始化：源顶点到自身的距离为 0，到其他顶点的距离为无穷大
创建一个优先队列，包含所有未访问的顶点，按照距离排序
每次从队列中取出距离最小的顶点，并对其所有未访问的邻接顶点进行松弛操作
重复步骤 3，直到队列为空

实现：

python

import heapq

def dijkstra(graph, n, source):
    # 初始化距离
    dist = [float('inf')] * n
    dist[source] = 0
    
    # 前驱节点，用于重建路径
    predecessor = [None] * n
    
    # 优先队列，存储 (距离, 顶点)
    pq = [(0, source)]
    
    # 记录顶点是否已处理
    processed = [False] * n
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if processed[u]:
            continue
        
        processed[u] = True
        
        for v, weight in graph[u]:
            if not processed[v] and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                predecessor[v] = u
                heapq.heappush(pq, (dist[v], v))
    
    return dist, predecessor

时间复杂度：

使用二叉堆： $O(|E| \log |V|)$
使用斐波那契堆： $O(|E| + |V| \log |V|)$

适用场景：

图中所有边权非负
需要高效计算单源最短路径
稠密图或稀疏图都适用

算法比较

算法	时间复杂度	处理负权边	检测负权环	适用场景
Bellman-Ford	$O(	V	\cdot	E
DAG 最短路径	$O(	V	+	E
Dijkstra	$O(	E	\log	V

所有点对最短路径

所有点对最短路径问题是指，计算图中任意两个顶点之间的最短路径。

Floyd-Warshall 算法

Floyd-Warshall 算法是一种动态规划算法，用于解决所有点对最短路径问题，可以处理包含负权边的图（但不能有负权环）。

算法思想：

对于任意两点 $i$ 和 $j$ ，考虑经过中间点 $k$ 是否能缩短 $i$ 到 $j$ 的距离
动态规划状态： $dp[k][i][j]$ 表示仅使用前 $k$ 个顶点作为中间点时，从 $i$ 到 $j$ 的最短路径长度

算法步骤：

初始化： $dp[0][i][j]$ 为 $i$ 到 $j$ 的直接边权，如果不存在边则为无穷大
对于每个 $k$ 从 1 到 $|V|$ ，更新 $dp[k][i][j] = \min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])$
最终 $dp[|V|][i][j]$ 即为 $i$ 到 $j$ 的最短路径长度

简化实现：

python

def floyd_warshall(graph, n):
    # 初始化距离矩阵
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
    
    # 设置对角线元素为 0
    for i in range(n):
        dist[i][i] = 0
    
    # 设置直接边的权值
    for u in range(n):
        for v, weight in graph[u]:
            dist[u][v] = weight
    
    # Floyd-Warshall 算法
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # 检测负权环
    for i in range(n):
        if dist[i][i] < 0:
            return None  # 存在负权环
    
    return dist

时间复杂度： $O(|V|^3)$

空间复杂度： $O(|V|^2)$

适用场景：

需要计算所有点对之间的最短路径
图中可能包含负权边（但不能有负权环）
图比较稠密
图的规模不是特别大（顶点数 $\leq 1000$ ）

实例：考虑下面的带权有向图，边上的数字表示权值：

初始距离矩阵：

    0   3   ∞   ∞
    ∞   0   ∞   2
    ∞   ∞   0   ∞
    ∞   ∞   1   0

Floyd-Warshall 算法的执行过程：

以顶点 0 为中间点，更新距离矩阵（没有变化）
以顶点 1 为中间点，更新：
- dist[0][3] = min(∞, 3 + 2) = 5
以顶点 2 为中间点，更新：
- 没有变化
以顶点 3 为中间点，更新：
- dist[1][2] = min(∞, 2 + 1) = 3
- dist[0][2] = min(∞, 5 + 1) = 6

最终距离矩阵：

    0   3   6   5
    ∞   0   3   2
    ∞   ∞   0   ∞
    ∞   ∞   1   0

这表示从顶点 0 到顶点 2 的最短距离是 6，路径是 0 → 1 → 3 → 2。

Johnson 算法

Johnson 算法结合了 Bellman-Ford 算法和 Dijkstra 算法，用于解决所有点对最短路径问题，特别适用于稀疏图。

算法思想：

使用 Bellman-Ford 算法计算一组顶点权重，用于将图中的所有边权重重新赋值为非负值
然后对每个顶点，使用 Dijkstra 算法计算其到其他所有顶点的最短路径

算法步骤：

创建一个新图，添加一个超级源点 $s$ ，从 $s$ 到原图中的每个顶点添加一条权值为 0 的边
对新图运行 Bellman-Ford 算法，得到从 $s$ 到每个顶点 $v$ 的最短距离 $h(v)$
如果 Bellman-Ford 算法检测到负权环，返回错误
对原图中的每条边 $(u, v)$ 重新赋值： $w'(u, v) = w(u, v) + h(u) - h(v)$
对每个顶点 $u$ ，使用 Dijkstra 算法计算 $u$ 到所有其他顶点的最短路径
对于每对顶点 $(u, v)$ ，将最短路径长度还原： $d(u, v) = d'(u, v) - h(u) + h(v)$

实现：

python

import heapq

def johnson(graph, n):
    # 步骤 1: 添加超级源点
    extended_graph = [[] for _ in range(n + 1)]
    for u in range(n):
        for v, weight in graph[u]:
            extended_graph[u].append((v, weight))
        extended_graph[n].append((u, 0))  # 从超级源点到所有顶点的边
    
    # 步骤 2: 运行 Bellman-Ford 算法
    h = [float('inf')] * (n + 1)
    h[n] = 0
    
    for _ in range(n):
        for u in range(n + 1):
            for v, weight in extended_graph[u]:
                if h[u] != float('inf') and h[u] + weight < h[v]:
                    h[v] = h[u] + weight
    
    # 检测负权环
    for u in range(n + 1):
        for v, weight in extended_graph[u]:
            if h[u] != float('inf') and h[u] + weight < h[v]:
                return None  # 存在负权环
    
    # 步骤 3-4: 重新赋值边权
    reweighted_graph = [[] for _ in range(n)]
    for u in range(n):
        for v, weight in graph[u]:
            reweighted_graph[u].append((v, weight + h[u] - h[v]))
    
    # 步骤 5: 对每个顶点运行 Dijkstra 算法
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
    
    for source in range(n):
        # Dijkstra 算法
        dist[source][source] = 0
        pq = [(0, source)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            if d > dist[source][u]:
                continue
            
            for v, weight in reweighted_graph[u]:
                if dist[source][u] + weight < dist[source][v]:
                    dist[source][v] = dist[source][u] + weight
                    heapq.heappush(pq, (dist[source][v], v))
    
    # 步骤 6: 还原最短路径长度
    for u in range(n):
        for v in range(n):
            if dist[u][v] != float('inf'):
                dist[u][v] = dist[u][v] - h[u] + h[v]
    
    return dist

时间复杂度： $O(|V|^2 \log |V| + |V||E|)$

适用场景：

需要计算所有点对之间的最短路径
图中可能包含负权边（但不能有负权环）
图比较稀疏（ $|E| \ll |V|^2$ ）

Floyd-Warshall 与 Johnson 算法比较

特性	Floyd-Warshall	Johnson
时间复杂度	$O(	V
适用图类型	稠密图	稀疏图
处理负权边	✓	✓
检测负权环	✓	✓
实现难度	简单	中等
空间复杂度	$O(	V

最大网络流

网络流问题是图论中的一类重要问题，涉及在流网络中寻找最大流量或最小割等。

基本概念

流网络：一个带权有向图 $G = (V, E)$ ，其中每条边 $(u, v) \in E$ 有一个非负容量 $c(u, v) \geq 0$
源点 (source)：流的起始点，通常记为 $s$
汇点 (sink)：流的终止点，通常记为 $t$
流 (flow)：函数 $f: V \times V \rightarrow \mathbb{R}$ $f : V \times V \to R$ 满足以下条件：
- 容量限制：对于所有 $u, v \in V$ ， $0 \leq f(u, v) \leq c(u, v)$
- 流量守恒：对于所有 $u \in V - \{s, t\}$ ， $\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)$
网络流值：从源点流出的流量总和： $|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)$
最大流：流网络中值最大的流

残余网络

残余网络 $G_f = (V, E_f)$ 表示在当前流 $f$ 下，网络中还能容纳的额外流量。

对于原图中的每条边 $(u, v) \in E$ ，如果 $f(u, v) < c(u, v)$ ，则在 $G_f$ 中添加一条容量为 $c(u, v) - f(u, v)$ 的边 $(u, v)$
对于原图中的每条边 $(u, v) \in E$ ，如果 $f(u, v) > 0$ ，则在 $G_f$ 中添加一条容量为 $f(u, v)$ 的反向边 $(v, u)$

增广路径

增广路径是残余网络 $G_f$ 中从源点 $s$ 到汇点 $t$ 的一条路径，表示可以增加的流量。

增广路径的瓶颈容量是路径上最小的边容量
沿着增广路径增加流量，可以增加网络的总流量

Ford-Fulkerson 方法

Ford-Fulkerson 方法是解决最大流问题的基本框架，基于增广路径的思想。

算法思想：

初始时，所有边的流量为 0
不断寻找残余网络中的增广路径，并沿着路径增加流量
当不存在增广路径时，当前流即为最大流

算法步骤：

初始化所有边的流量为 0
在残余网络中寻找一条从源点 $s$ 到汇点 $t$ 的增广路径
计算增广路径的瓶颈容量
沿着增广路径增加流量
更新残余网络
重复步骤 2-5，直到不存在增广路径

实现：

python

def ford_fulkerson(graph, source, sink):
    n = len(graph)
    flow = 0
    
    # 初始化流量为 0
    residual_graph = [[0 for _ in range(n)] for _ in range(n)]
    for u in range(n):
        for v, capacity in graph[u]:
            residual_graph[u][v] = capacity
    
    # 寻找增广路径
    def bfs():
        visited = [False] * n
        queue = [source]
        visited[source] = True
        parent = [-1] * n
        
        while queue:
            u = queue.pop(0)
            
            for v in range(n):
                if not visited[v] and residual_graph[u][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
        
        # 如果汇点被访问到，则存在增广路径
        return visited[sink], parent
    
    # Ford-Fulkerson 算法
    while True:
        path_exists, parent = bfs()
        
        if not path_exists:
            break
        
        # 寻找增广路径的瓶颈容量
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, residual_graph[u][v])
            v = u
        
        # 更新残余网络
        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= path_flow
            residual_graph[v][u] += path_flow  # 反向边
            v = u
        
        flow += path_flow
    
    return flow

时间复杂度：

如果使用 BFS 寻找增广路径（Edmonds-Karp 算法）： $O(|V| \cdot |E|^2)$
如果增广路径的选择是任意的： $O(|E| \cdot |f|)$ ，其中 $|f|$ 是最大流的值

实例：考虑下面的流网络，边上的数字表示容量：

         (2)
      0 ----> 2
     / \     / \
(3) /   \(3)/   \ (2)
   /     \/     v
  s       1 ----> t
   \     /       ^
(3) \   /(2)     / (3)
     v v        /
      3 -------

其中 s 是源点，t 是汇点。

Ford-Fulkerson 算法的执行过程：

找到增广路径 s → 0 → 2 → t，流量为 min(3, 2, 2) = 2
- 更新残余网络，总流量 = 2
找到增广路径 s → 0 → 1 → t，流量为 min(3-2, 3, 2) = 1
- 更新残余网络，总流量 = 2 + 1 = 3
找到增广路径 s → 3 → t，流量为 min(3, 3) = 3
- 更新残余网络，总流量 = 3 + 3 = 6
没有更多的增广路径，算法终止

最大流的值为 6。

最大二分匹配

二分匹配问题是网络流的一个重要应用，可以通过最大流算法来解决。

基本概念

二分图：顶点集合可以划分为两个互不相交的子集 $L$ 和 $R$ ，使得每条边连接的两个顶点分别来自 $L$ 和 $R$
匹配：边的一个子集，其中任意两条边不共享顶点
最大匹配：具有最大边数的匹配

转化为最大流问题

二分匹配问题可以转化为最大流问题：

创建一个源点 $s$ 和一个汇点 $t$
对于二分图中的每个左侧顶点 $u \in L$ ，添加一条容量为 1 的边 $(s, u)$
对于二分图中的每个右侧顶点 $v \in R$ ，添加一条容量为 1 的边 $(v, t)$
对于二分图中的每条边 $(u, v)$ ，添加一条容量为 1 的边 $(u, v)$
求解该流网络的最大流，最大流的值即为最大匹配的大小

实例：考虑下面的二分图，左侧是工人，右侧是任务：

邻接表表示（每个工人可以执行的任务）：

graph = [
    [0, 1],  # 工人0可以执行任务0和任务1
    [1, 2],  # 工人1可以执行任务1和任务2
    [0, 1]   # 工人2可以执行任务0和任务1
]

将二分匹配问题转化为最大流问题：

创建源点s和汇点t
从源点s连接到所有工人（容量为1）
从所有任务连接到汇点t（容量为1）
根据工人能力添加从工人到任务的边（容量为1）

使用Ford-Fulkerson算法求解最大流，找到以下增广路径：

s → 工人0 → 任务0 → t，流量为1
s → 工人1 → 任务2 → t，流量为1
s → 工人2 → 任务1 → t，流量为1

最终匹配结果：

工人0 ↔ 任务0
工人1 ↔ 任务2
工人2 ↔ 任务1

最大匹配大小为3。

实现：


### 图论算法实例小结

本文为各种图论算法提供了详细的实例，帮助理解算法的工作原理：

1. **图的遍历**：
   - DFS：通过递归深入探索图的分支，展示了遍历顺序和回溯过程
   - BFS：通过队列按层次访问顶点，展示了距离起点不同距离的顶点访问顺序

2. **拓扑排序**：
   - 使用Kahn算法处理课程依赖关系的有向无环图，展示了顶点的合法排序顺序

3. **强连通分量**：
   - 使用Kosaraju算法识别有向图中的循环依赖组，展示了两次DFS的执行过程

4. **最小生成树**：
   - Kruskal算法：按边权排序，贪心选择不形成环的最小权边
   - Prim算法：从一个顶点开始，贪心选择连接到当前树的最小权边

5. **单源最短路径**：
   - Bellman-Ford算法：通过迭代松弛操作处理带负权边的图
   - DAG最短路径：利用拓扑排序简化最短路径计算
   - Dijkstra算法：使用优先队列处理非负权图的单源最短路径

6. **所有点对最短路径**：
   - Floyd-Warshall算法：动态规划方法计算所有顶点对之间的最短路径
   - Johnson算法：结合Bellman-Ford和Dijkstra算法处理稀疏图的所有点对最短路径

7. **网络流**：
   - Ford-Fulkerson方法：基于增广路径的最大流算法
   - 最大二分匹配：将二分匹配问题转化为最大流问题求解

这些实例展示了算法的实际执行过程，帮助读者更直观地理解算法的工作原理和应用场景。

算法设计与分析归纳 ​

2021年考试题解答 ​

简述三种算法效率符号 ​

知识点：算法时间复杂度分析 ​

两种随机化算法及特征 ​

Las Vegas 算法 ​

核心特征： ​

示例： ​

时间复杂度： ​

Monte Carlo 算法 ​

核心特征： ​

示例： ​

时间复杂度： ​

字符编码 & 文本文件最短储存，字符编码的特点 ​

知识点：字符编码与文本压缩 ​

分治法子问题的特点 ​

知识点：分治法的核心思想 ​

证明题：很简单的问题 ​

知识点：算法正确性的证明 ​

设计题：分治法求 n 元素数组中数量超过一半的元素 ​

知识点：Boyer-Moore 投票算法 ​

动态规划：批了一个称重外皮完全背包问题 ​

知识点：完全背包问题 ​

贪心：教室安排（原题） ​

知识点：区间调度问题 ​

图论：最大流和最小割 & 3 * 3 的 Floyd ​

知识点：最大流与最小割 ​

知识点：Floyd-Warshall 算法 ​

主方法（Master Method）的三种情况 ​

1. 情况 1：f(n)=O(nlogba−ϵ)f(n)=O(n^{\log_b a-\epsilon})f(n)=O(n​log​b​​a−ϵ​​) ​

2. 情况 2：f(n)=Θ(nlogba)f(n)=\Theta(n^{\log_b a})f(n)=Θ(n​log​b​​a​​) ​

3. 情况 3：f(n)=Ω(nlogba+ϵ)f(n)=\Omega(n^{\log_b a+\epsilon})f(n)=Ω(n​log​b​​a+ϵ​​) ​

实例分析 ​

总结 ​

基于比较的排序算法的理论下界 简要证明思路 ​

1. 决策树是什么？ ​

2. 有多少种可能的排列？ ​

3. 决策树的高度是多少？ ​

4. 估计 log2(n!)\log_2(n!)log​2​​(n!) 的下界 ​

✅ 结论 ​

6种排序算法比较和示例 ​

排序算法对比表 ​

1. 插入排序（Insertion Sort） ​

2. 归并排序（Merge Sort） ​

3. 快速排序（Quick Sort） ​

4. 基数排序（Radix Sort） ​

5. 计数排序（Counting Sort） ​

6. 桶排序（Bucket Sort） ​

分治法 ​

分治法的开销分析 ​

常见分治算法及时间复杂度 ​

优缺点分析 ​

二分搜索 ​

算法思想： ​

时间复杂度： ​

空间复杂度： ​

标准定义与朴素分治矩阵乘法 ​

标准矩阵乘法定义： ​

朴素分治策略详解： ​

递归式推导： ​

时间复杂度： ​

Strassen矩阵乘法算法 ​

算法详细步骤： ​

正确性证明： ​

计算量分析： ​

递归式推导： ​

时间复杂度： ​

实际应用考量： ​

实例演示： ​

大整数乘法 ​

Karatsuba算法详解 ​

基本思想 ​

算法详细步骤 ​

递归实现 ​

时间复杂度分析 ​

实例演示 ​

优化与应用 ​

最近点对问题 ​

问题定义 ​

分治算法详解 ​

算法设计与分析归纳

2021年考试题解答

简述三种算法效率符号

知识点：算法时间复杂度分析

两种随机化算法及特征

Las Vegas 算法

核心特征：

示例：

时间复杂度：

Monte Carlo 算法

核心特征：

示例：

时间复杂度：

字符编码 & 文本文件最短储存，字符编码的特点

知识点：字符编码与文本压缩

分治法子问题的特点

知识点：分治法的核心思想

证明题：很简单的问题

知识点：算法正确性的证明

设计题：分治法求 n 元素数组中数量超过一半的元素

知识点：Boyer-Moore 投票算法

动态规划：批了一个称重外皮完全背包问题

知识点：完全背包问题

贪心：教室安排（原题）

知识点：区间调度问题

图论：最大流和最小割 & 3 * 3 的 Floyd

知识点：最大流与最小割

知识点：Floyd-Warshall 算法

主方法（Master Method）的三种情况

1. 情况 1： $f(n)=O(n^{\log_b a-\epsilon})$

2. 情况 2： $f(n)=\Theta(n^{\log_b a})$

3. 情况 3： $f(n)=\Omega(n^{\log_b a+\epsilon})$

实例分析

总结

基于比较的排序算法的理论下界简要证明思路

1. 决策树是什么？

2. 有多少种可能的排列？

3. 决策树的高度是多少？

4. 估计 $\log_2(n!)$ 的下界

✅ 结论

6种排序算法比较和示例

排序算法对比表

1. 插入排序（Insertion Sort）

2. 归并排序（Merge Sort）

3. 快速排序（Quick Sort）

4. 基数排序（Radix Sort）

5. 计数排序（Counting Sort）

6. 桶排序（Bucket Sort）

分治法

分治法的开销分析

常见分治算法及时间复杂度

优缺点分析

二分搜索

算法思想：

时间复杂度：

空间复杂度：

标准定义与朴素分治矩阵乘法

标准矩阵乘法定义：

朴素分治策略详解：

递归式推导：

时间复杂度：

Strassen矩阵乘法算法

算法详细步骤：

正确性证明：

计算量分析：

递归式推导：

时间复杂度：

实际应用考量：

实例演示：

大整数乘法

Karatsuba算法详解

基本思想

算法详细步骤

递归实现

时间复杂度分析

实例演示

优化与应用

最近点对问题

问题定义

分治算法详解