算法概览

需要先区分三个概念：

• 算法设计思想：怎样从问题得到算法，例如分治、动态规划、贪心。

• 具体算法：解决某类问题的成熟步骤，例如归并排序、Dijkstra。

• 数据结构：用于组织和维护数据，例如堆、并查集、线段树。

下面按照“设计思想—问题领域—高级方法”进行分类。

一、直接求解类方法

模拟法

按照题目给定的规则，依次还原事件发生的过程。

适用信号：

• 题目规则已经完全确定；

• 不需要寻找最优决策；

• 只需要按照时间或操作顺序执行。

典型问题：

• 地铁公交优惠票；

• 日期计算；

• 排队过程；

• 棋盘移动；

• 缓存和调度规则。

核心步骤：

确定状态 → 读取事件 → 按规则更新状态 → 输出结果

---

枚举法

列出所有可能情况，逐一检查。

适用信号：

• 候选数量不大；

• 数据规模较小；

• 暂时没有发现更好的结构。

常见形式：

• 枚举一个变量；

• 枚举两个变量；

• 枚举区间；

• 枚举子集；

• 枚举排列。

例如，两数之和可以枚举所有数对：

$$O(n^2)$$

枚举法通常是设计其他算法的起点：

先写出完整枚举，再寻找重复计算和无效计算。

---

暴力搜索法

把所有可能的选择构造成一棵搜索树，遍历所有可能解。

常见形式：

• DFS

• BFS

• 子集搜索

• 排列搜索

• 状态空间搜索

暴力搜索与普通枚举的区别不严格。一般来说，枚举更强调“列出候选”，搜索更强调“从一个状态转移到另一个状态”。

---

查表与预处理法

提前计算将来会反复使用的信息。

典型方法：

• 前缀和；

• 后缀和；

• 差分；

• 稀疏表；

• 倍增；

• 预计算质数；

• 记忆化；

• 离线查询。

例如区间和：

$$sum(l,r)=prefix[r]-prefix[l-1]$$

将每次 $O(n)$ 的区间求和降为 $O(1)$。

---

二、经典算法设计范式

分治法

把一个大问题分解成若干规模更小、相对独立的同类问题，分别求解后合并。

基本过程：

分解 → 递归求解 → 合并结果

典型算法：

• 归并排序；

• 快速排序；

• 二分查找；

• 最近点对；

• 大整数乘法；

• 快速傅里叶变换。

典型递推式：

$$T(n)=aT(n/b)+f(n)$$

适用信号：

• 问题具有递归结构；

• 子问题相对独立；

• 子问题结果容易合并。

---

减治法

每次把问题缩小一部分，而不是拆成多个子问题。

常见形式：

• 减少一个元素；

• 减少一个常数规模；

• 将规模减半；

• 缩小搜索范围。

典型算法：

• 插入排序；

• 拓扑排序；

• 二分查找；

• 欧几里得算法。

分治与减治的区别是：

• 分治：产生多个子问题；

• 减治：主要进入一个更小的子问题。

---

动态规划法

把原问题分解成具有重叠关系的子问题，并保存已经计算过的结果。

适用条件：

• 最优子结构；

• 重叠子问题；

• 状态能够完整描述未来决策所需的信息。

统一设计步骤：

1. 定义状态；

2. 确定选择；

3. 写状态转移；

4. 设置初始状态；

5. 确定计算顺序；

6. 找到最终答案；

7. 优化时间或空间。

常见类型：

• 线性 DP；

• 背包 DP；

• 区间 DP；

• 树形 DP；

• 数位 DP；

• 状态压缩 DP；

• 概率 DP；

• 计数 DP；

• DAG 上的 DP；

• 博弈 DP。

典型问题：

• 0-1 背包；

• 最长公共子序列；

• 最长递增子序列；

• 矩阵链乘法；

• 编辑距离；

• 最优二叉搜索树。

动态规划的核心是：

合并相同状态，避免重复计算。

---

记忆化搜索

用递归搜索描述问题，同时把已经计算过的状态保存下来。

它可以理解为：

自顶向下的动态规划。

与递推 DP 的区别：

---

贪心法

每一步选择当前看来最好的方案，并且证明这个选择不会破坏全局最优性。

典型算法：

• 区间调度；

• Huffman 编码；

• Kruskal；

• Prim；

• Dijkstra；

• 部分背包；

• 活动选择。

常用证明方法：

• 交换论证；

• 领先法；

• 数学归纳法；

• 割性质；

• 环性质；

• 拟阵理论。

关键问题是：

能否把任意最优解调整为包含当前贪心选择的最优解？

---

回溯法

按照深度优先方式尝试不同选择，发现当前部分解不可能成功时立即返回。

统一结构：

回溯(当前状态):
    如果形成完整解:
        记录答案
        返回

    对每个候选选择:
        如果选择合法:
            做选择
            递归
            撤销选择

典型问题：

• N 皇后；

• 数独；

• 全排列；

• 子集和；

• 图着色；

• 组合生成；

• 迷宫路径；

• 约束满足问题。

回溯的核心是：

系统枚举搜索空间，并删除不可能成功的分支。

---

分支限界法

与回溯类似，也在状态空间中搜索，但重点是使用“上界”或“下界”判断某个分支是否可能超过当前最优答案。

典型过程：

维护当前最优答案
计算分支可能达到的最好结果
如果仍然不如当前答案，则删除整个分支

常见问题：

• 旅行商问题；

• 0-1 背包；

• 任务分配；

• 整数规划；

• 调度问题。

区别可以简单理解为：

• 回溯主要剪掉“不合法”的分支；

• 分支限界主要剪掉“不可能更优”的分支。

---

三、利用问题性质的方法

二分查找法

在有序范围中不断排除一半搜索空间。

适用条件：

• 数据有序；

• 或者某个判定具有单调性。

典型形式：

• 查找某个元素；

• 查找第一个满足条件的位置；

• 查找最后一个满足条件的位置；

• 二分答案。

复杂度通常为：

$$O(\log n)$$

---

二分答案法

不是直接寻找答案，而是猜测一个答案 $x$，再判断它是否可行。

统一过程：

猜测答案 x
调用 check(x)
根据真假缩小答案范围

适用信号：

• 求“最大值的最小值”；

• 求“最小值的最大值”；

• 答案是否可行具有单调性。

典型问题：

• 最小最大工作量；

• 最大化最小距离；

• 木材切割；

• 最小运输能力；

• 生产时间问题。

---

双指针法

使用两个指针共同扫描数据，避免重复枚举。

常见形式：

• 左右指针；

• 快慢指针；

• 同向双指针；

• 相向双指针；

• 多路归并指针。

典型问题：

• 有序数组两数之和；

• 删除重复元素；

• 合并有序数组；

• 链表判环；

• 最长连续区间。

复杂度经常从 $O(n^2)$ 降为 $O(n)$。

---

滑动窗口法

维护一个连续区间，根据条件移动左右边界。

基本结构：

右端点不断扩张
更新窗口状态
条件不满足时移动左端点
记录答案

典型问题：

• 最长无重复子串；

• 长度最小的满足条件子数组；

• 固定长度窗口最大值；

• 字符频率匹配；

• 连续区间统计。

滑动窗口实际上是同向双指针的一种重要形式。

---

前缀和与差分法

前缀和

适合反复查询区间信息：

$$prefix[i]=a_1+a_2+\cdots+a_i$$

区间和为：

$$sum(l,r)=prefix[r]-prefix[l-1]$$

差分

适合反复进行区间修改。

例如给区间 $[l,r]$ 全部加 $x$：

diff[l] += x
diff[r+1] -= x

最后求一次前缀和即可恢复结果。

---

离线算法

先收集所有查询，再统一排序或重新组织处理顺序。

与之相对的是在线算法：

• 在线：输入一条，立即回答一条；

• 离线：看完所有问题后统一回答。

典型离线算法：

• Mo 算法；

• 离线并查集；

• 离线排序查询；

• CDQ 分治；

• Tarjan 离线最近公共祖先。

---

随机化算法

在算法中主动使用随机数。

常见类型：

• Las Vegas 算法：答案一定正确，运行时间具有随机性；

• Monte Carlo 算法：运行时间可控，但存在很小的错误概率。

典型算法：

• 随机快速排序；

• 随机选择；

• Miller–Rabin 素数测试；

• 随机哈希；

• 随机采样。

---

四、搜索与状态空间方法

深度优先搜索

沿一个方向尽可能深入，无法继续时返回。

适合：

• 连通性；

• 路径枚举；

• 拓扑结构；

• 回溯问题；

• 树和图的遍历。

实现方式：

• 递归；

• 显式栈。

---

广度优先搜索

从起点开始，按距离一层一层扩展。

适合：

• 无权图最短路；

• 最少操作次数；

• 状态转换问题；

• 层次遍历。

基本数据结构是队列。

---

双向搜索

同时从起点和终点搜索，当两边相遇时停止。

适合：

• 起点和终点都明确；

• 状态转移可以逆向；

• 普通 BFS 搜索空间较大。

它可以将搜索深度从 $d$ 降为两边各约 $d/2$。

---

启发式搜索

使用一个估价函数判断哪些状态更有希望。

典型算法：

• 最佳优先搜索；

• A*；

• IDA*。

A* 常用评价函数：

$$f(n)=g(n)+h(n)$$

其中：

• $g(n)$：从起点到当前状态的实际代价；

• $h(n)$：从当前状态到目标的估计代价。

---

迭代加深搜索

限制 DFS 的最大深度，如果没有找到答案，就逐渐增加深度限制。

它结合了：

• DFS 较低的空间消耗；

• BFS 按深度寻找答案的特点。

典型方法：

• IDDFS；

• IDA*。

---

五、排序与选择方法

基于比较的排序

典型算法：

• 冒泡排序；

• 选择排序；

• 插入排序；

• 希尔排序；

• 归并排序；

• 快速排序；

• 堆排序。

比较排序的一般下界为：

$$\Omega(n\log n)$$

---

非比较排序

利用键值范围或数位结构排序。

典型算法：

• 计数排序；

• 桶排序；

• 基数排序。

在条件合适时，可以达到接近：

$$O(n)$$

但通常需要额外的值域或分布假设。

---

选择算法

不要求完全排序，只寻找第 $k$ 小、第 $k$ 大或中位数。

典型算法：

• 快速选择；

• 堆选择；

• 中位数的中位数；

• 二分答案；

• 有序结构维护。

---

六、图算法

图算法既是一类具体算法，也是一种重要的问题建模方式。

图的遍历

• DFS；

• BFS。

解决：

• 可达性；

• 连通分量；

• 环检测；

• 路径存在性；

• 图的层次。

---

最短路径

---

最小生成树

让所有顶点连通，并使总边权最小。

典型算法：

• Kruskal；

• Prim；

• Borůvka。

常见应用：

• 网络布线；

• 道路建设；

• 最低连接成本；

• 聚类。

---

拓扑排序

用于有向无环图中的依赖关系排序。

典型算法：

• Kahn 入度法；

• DFS 后序法。

常见问题：

• 课程先修关系；

• 工程依赖；

• 任务调度；

• 编译顺序。

---

并查集

维护集合之间的合并与查询。

核心操作：

• find：查询元素属于哪个集合；

• union：合并两个集合。

优化方法：

• 路径压缩；

• 按秩合并；

• 按大小合并。

典型应用：

• 动态连通性；

• Kruskal；

• 判断环；

• 合并账户。

并查集严格来说是数据结构，但经常作为算法方法使用。

---

强连通分量

在有向图中寻找相互可达的最大顶点集合。

典型算法：

• Tarjan；

• Kosaraju。

常用于：

• 缩点；

• 依赖分析；

• 2-SAT；

• 图结构简化。

---

割点、桥与双连通分量

分析图中哪些顶点或边对连通性至关重要。

典型算法：

• Tarjan DFS；

• Low-link 方法。

应用：

• 网络脆弱性；

• 关键节点；

• 关键道路；

• 图的分解。

---

二分图匹配

解决两个集合之间的配对问题。

典型算法：

• 匈牙利算法；

• Hopcroft–Karp；

• 网络流建模。

典型应用：

• 人员与任务分配；

• 学生与课程匹配；

• 机器与作业匹配。

---

网络流

在容量受限的网络中传输最大流量或最小费用。

典型问题：

• 最大流；

• 最小割；

• 最小费用最大流；

• 有上下界的网络流。

典型算法：

• Ford–Fulkerson；

• Edmonds–Karp；

• Dinic；

• Push–Relabel。

许多匹配、分配、调度问题都可以转化为网络流。

---

七、字符串算法

字符串匹配

在文本中寻找模式串。

典型算法：

• 暴力匹配；

• KMP；

• Boyer–Moore；

• Rabin–Karp；

• Z 算法。

---

Trie 字典树

按照字符路径保存多个字符串。

适合：

• 前缀查询；

• 字典匹配；

• 自动补全；

• 异或问题中的二进制 Trie。

---

AC 自动机

在一个长文本中同时匹配多个模式串。

它可以理解为：

Trie + 失败指针。

常见应用：

• 多关键词搜索；

• 敏感词匹配；

• 文本扫描。

---

字符串哈希

将字符串映射成数值，用于快速比较子串。

适合：

• 子串相等判断；

• 回文判断；

• 重复子串；

• 字符串去重。

需要注意哈希冲突。

---

后缀结构

包括：

• 后缀数组；

• 后缀树；

• 后缀自动机。

适合：

• 最长重复子串；

• 不同子串数量；

• 多字符串公共子串；

• 子串出现次数。

---

回文字符串算法

典型方法：

• 中心扩展；

• 动态规划；

• Manacher；

• 回文自动机。

---

八、数论算法

最大公约数与扩展欧几里得

欧几里得算法：

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

扩展欧几里得还可以求：

$$ax+by=\gcd(a,b)$$

用于：

• 模逆元；

• 线性同余方程；

• 中国剩余定理。

---

素数相关方法

• 试除法；

• 埃拉托斯特尼筛法；

• 线性筛；

• Miller–Rabin；

• Pollard Rho。

---

快速幂与矩阵快速幂

快速计算：

$$a^n$$

复杂度为：

$$O(\log n)$$

矩阵快速幂常用于：

• 线性递推；

• 斐波那契；

• 状态转移加速；

• 固定转移的计数问题。

---

模运算与组合数学

包括：

• 模逆元；

• 费马小定理；

• 欧拉定理；

• 组合数递推；

• Lucas 定理；

• 容斥原理；

• 抽屉原理；

• 生成函数。

---

中国剩余定理

求解多个模方程组成的同余方程组：

$$x\equiv a_i\pmod{m_i}$$

---

九、计算几何算法

基本几何计算

• 点积；

• 叉积；

• 方向判断；

• 点在线段上；

• 线段相交；

• 点到直线距离；

• 多边形面积。

---

凸包

寻找包含所有点的最小凸多边形。

典型算法：

• Graham Scan；

• Andrew 单调链。

---

扫描线

把二维几何问题按照某个方向逐步扫描，并维护当前活动对象。

典型应用：

• 区间覆盖；

• 矩形面积并；

• 线段相交；

• 最近点对；

• 平面事件处理。

扫描线通常需要配合：

• 排序；

• 堆；

• 平衡树；

• 线段树。

---

旋转卡壳

在凸包上利用单调性移动指针。

典型问题：

• 凸包直径；

• 最远点对；

• 最小包围矩形。

---

十、数据结构辅助方法

数据结构不是独立的算法范式，但很多高效算法必须依赖数据结构。

哈希法

使用哈希表实现接近 $O(1)$ 的查找、插入和删除。

典型问题：

• 两数之和；

• 频率统计；

• 去重；

• 状态记录；

• 记忆化搜索。

---

栈与单调栈

普通栈适用于：

• 括号匹配；

• 表达式求值；

• DFS；

• 撤销操作。

单调栈适用于：

• 下一个更大元素；

• 柱状图最大矩形；

• 每个元素左右第一个更大或更小的位置。

---

队列、双端队列与单调队列

适用于：

• BFS；

• 事件处理；

• 滑动窗口；

• 0-1 BFS；

• 区间最大值或最小值。

---

堆与优先队列

支持快速取得当前最小值或最大值。

典型应用：

• Dijkstra；

• Prim；

• Top-K；

• 任务调度；

• 多路归并；

• 动态中位数。

---

平衡搜索树

支持有序集合上的：

• 插入；

• 删除；

• 查找；

• 前驱；

• 后继；

• 排名。

典型结构：

• AVL 树；

• 红黑树；

• Treap；

• Splay。

---

树状数组

支持：

• 单点修改；

• 前缀查询；

• 区间和；

• 逆序对统计。

时间复杂度通常为：

$$O(\log n)$$

---

线段树

维护区间信息，并支持修改与查询。

常见功能：

• 区间和；

• 最大值和最小值；

• 区间加法；

• 区间赋值；

• 查询最早满足条件的位置。

复杂度通常为：

$$O(\log n)$$

---

稀疏表

经过预处理后，快速回答静态区间查询。

典型应用：

• 区间最大值；

• 区间最小值；

• 区间 GCD。

预处理：

$$O(n\log n)$$

查询：

$$O(1)$$

但通常不支持修改。

---

可持久化数据结构

保留数据结构的历史版本。

典型结构：

• 可持久化线段树；

• 可持久化 Trie；

• 可持久化并查集。

应用：

• 查询历史状态；

• 区间第 $k$ 小；

• 版本管理。

---

十一、优化问题中的高级方法

局部搜索

从一个可行解出发，不断进行局部调整。

例如：

• 交换两个元素；

• 修改一个决策；

• 调整一小段路径。

如果邻域中没有更优解，则停止。

缺点是可能陷入局部最优。

---

爬山算法

每次移动到附近更好的状态。

特点：

• 实现简单；

• 速度较快；

• 不保证获得全局最优解。

---

模拟退火

允许以一定概率接受较差解，从而跳出局部最优。

随着“温度”降低，接受较差解的概率逐渐减小。

适用于：

• 旅行商问题；

• 调度；

• 布局；

• 大规模组合优化。

---

遗传算法

模仿自然选择与遗传过程。

主要操作：

• 编码；

• 选择；

• 交叉；

• 变异；

• 适应度评价。

它属于启发式优化方法，通常不保证获得精确最优解。

---

蚁群、粒子群等群智能算法

利用多个个体之间的信息交换寻找较优解。

包括：

• 蚁群算法；

• 粒子群算法；

• 人工蜂群算法。

这类方法常用于连续优化和组合优化，但结果通常具有启发性。

---

近似算法

当精确最优解很难计算时，在多项式时间内获得接近最优的解。

关注近似比，例如：

$$\frac{\text{算法结果}}{\text{最优结果}}$$

典型应用：

• 顶点覆盖；

• 集合覆盖；

• 旅行商问题；

• 装箱问题。

---

参数化算法

不只以输入规模 $n$ 衡量难度，还选择一个较小参数 $k$。

目标复杂度形如：

$$f(k)\cdot n^{O(1)}$$

当 $k$ 很小时，即使问题一般情况下很难，也可能被高效求解。

---

在线算法

数据逐步到达，算法不能预先知道未来输入，必须立即决策。

典型问题：

• 缓存替换；

• 在线调度；

• 实时数据流；

• 在线匹配。

评价在线算法时经常使用竞争比。

---

流式算法

数据量太大，无法全部保存在内存中，只允许少量扫描和有限空间。

典型任务：

• 频率估计；

• 不同元素数量估计；

• 重元素检测；

• 随机采样。

---

并行与分布式算法

将计算任务分配给多个处理器或计算节点。

典型模式：

• 分治并行；

• MapReduce；

• 图并行；

• 数据并行；

• 流水线。

设计时还要考虑：

• 通信成本；

• 同步成本；

• 负载均衡；

• 容错。

---

十二、最适合课程教学的分类

如果用于“算法设计与分析”课程，不建议把所有内容平铺讲授。可以分成四个层次。

第一层：直接方法

• 模拟；

• 枚举；

• 暴力搜索；

• 排序；

• 哈希；

• 前缀和；

• 双指针；

• 滑动窗口。

这一层解决：

怎样把题目规则正确地变成程序？

第二层：核心设计范式

• 分治；

• 动态规划；

• 贪心；

• 回溯；

• 分支限界。

这一层解决：

怎样利用问题结构减少不必要的计算？

第三层：重要问题模型

• 图搜索；

• 最短路径；

• 最小生成树；

• 匹配；

• 网络流；

• 字符串匹配；

• 数论；

• 计算几何。

这一层解决：

能否把新问题转化成一个已经研究成熟的标准问题？

第四层：困难问题的处理

• 随机化；

• 近似算法；

• 参数化算法；

• 局部搜索；

• 模拟退火；

• 遗传算法；

• 在线算法；

• 并行算法。

这一层解决：

当精确算法太慢或数据无法完整获得时怎么办？

十三、一张核心速查表

十四、统一理解这些方法

大多数算法问题都可以抽象为四个组成部分：

$$\boxed{\text{状态}+\text{选择}+\text{转移}+\text{目标}}$$

不同算法的区别是处理状态空间的方式不同：

因此，课程中最值得建立的认识是：

算法设计不是记忆几十个互不相关的模板，而是识别问题结构，并选择合适的方法来组织、搜索、压缩或维护状态空间。