高级算法

围绕高级算法建立可解释、可验证的知识主线。

阅读起点

学习前先阅读：算法分析学习路线。

全书顺序

本书按知识依赖组织。主线先建立可运行的共同模型，再进入机制、工程边界和生产约束；维护与前沿内容明确标注，不改变主线的学习顺序。

第1章｜高级建模与分治优化

理解本章高级建模与分治优化的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 问题建模：状态、约束、目标与可行域：理解问题建模：状态、约束、目标与可行域的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 证明工具：归纳、交换论证、势能与对偶：理解证明工具：归纳、交换论证、势能与对偶的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 分治优化：CDQ、点分治、FFT 与并行分治：理解分治优化：CDQ、点分治、FFT 与并行分治的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 动态规划优化：单调队列、斜率优化与四边形不等式：理解动态规划优化：单调队列、斜率优化与四边形不等式的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 状态压缩与路径恢复：位压缩、方案计数与字典序：理解状态压缩与路径恢复：位压缩、方案计数与字典序的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第2章｜高级图算法

理解本章高级图算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 网络流：最大流最小割、Ford-Fulkerson 与 Dinic：理解网络流：最大流最小割、Ford-Fulkerson 与 Dinic的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 二分图匹配：匈牙利算法、KM 算法与稳定婚姻：理解二分图匹配：匈牙利算法、KM 算法与稳定婚姻的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 强连通分量：Tarjan、Kosaraju 与 2-SAT：理解强连通分量：Tarjan、Kosaraju 与 2-SAT的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 割点与桥：双连通分量与块树：理解割点与桥：双连通分量与块树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 最小割与全局最小割：Stoer-Wagner 与 Karger：理解最小割与全局最小割：Stoer-Wagner 与 Karger的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 平面图与欧拉路径：欧拉回路、哈密顿路径与图着色：理解平面图与欧拉路径：欧拉回路、哈密顿路径与图着色的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第3章｜字符串算法

理解本章字符串算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. KMP 与扩展 KMP：前缀函数、Z 算法与周期：理解KMP 与扩展 KMP：前缀函数、Z 算法与周期的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 字符串哈希：滚动哈希、双哈希与碰撞概率：理解字符串哈希：滚动哈希、双哈希与碰撞概率的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. Trie 与 AC 自动机：前缀树、失配指针与多模式：理解Trie 与 AC 自动机：前缀树、失配指针与多模式的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 后缀数组与 LCP：排序、倍增与最长公共子串：理解后缀数组与 LCP：排序、倍增与最长公共子串的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 后缀自动机：后缀链接、转移与子串识别：理解后缀自动机：后缀链接、转移与子串识别的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第4章｜计算几何

理解本章计算几何的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 几何基础：向量、叉积、点积与极角排序：理解几何基础：向量、叉积、点积与极角排序的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 凸包：Graham 扫描、Jarvis 步进与 Andrew 算法：理解凸包：Graham 扫描、Jarvis 步进与 Andrew 算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 线段相交：扫描线、Bentley-Ottmann 与平面分割：理解线段相交：扫描线、Bentley-Ottmann 与平面分割的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 最近点对与 Voronoi 图：分治、平面细分与对偶：理解最近点对与 Voronoi 图：分治、平面细分与对偶的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 旋转卡壳：直径、宽度与点对距离：理解旋转卡壳：直径、宽度与点对距离的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第5章｜随机化算法

理解本章随机化算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 随机化基础：Las Vegas、Monte Carlo 与错误概率：理解随机化基础：Las Vegas、Monte Carlo 与错误概率的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 随机快速排序与选择：期望复杂度与中位数的中位数：理解随机快速排序与选择：期望复杂度与中位数的中位数的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 哈希：全域哈希、完美哈希与布隆过滤器：理解哈希：全域哈希、完美哈希与布隆过滤器的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 采样与蒙特卡洛：拒绝采样、重要性采样与估算：理解采样与蒙特卡洛：拒绝采样、重要性采样与估算的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 概率数据结构：Count-Min Sketch、HyperLogLog 与 t-digest：理解概率数据结构：Count-Min Sketch、HyperLogLog 与 t-digest的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第6章｜近似算法与复杂度

理解本章近似算法与复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 近似算法基础：近似比、PTAS 与 APX：理解近似算法基础：近似比、PTAS 与 APX的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 贪心近似：集合覆盖、顶点覆盖与调度：理解贪心近似：集合覆盖、顶点覆盖与调度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 线性规划松弛：整数规划、松弛与舍入：理解线性规划松弛：整数规划、松弛与舍入的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. NP 完全：归约、SAT、Clique 与背包：理解NP 完全：归约、SAT、Clique 与背包的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 参数化复杂度：FPT、核化与树宽：理解参数化复杂度：FPT、核化与树宽的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第7章｜在线算法、并行与验证（第1段）

理解本章在线算法、并行与验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 在线算法：竞争比、滑雪租赁与 k-server：理解在线算法：竞争比、滑雪租赁与 k-server的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 缓存策略：LRU、FIFO、LFU 与竞争分析：理解缓存策略：LRU、FIFO、LFU 与竞争分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 并行算法：PRAM、并行前缀、归约与工作深度：理解并行算法：PRAM、并行前缀、归约与工作深度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 外存算法：I/O 模型、外部排序与缓存遗忘：理解外存算法：I/O 模型、外部排序与缓存遗忘的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 算法验证：对拍、压力测试、数据生成与反例构造：理解算法验证：对拍、压力测试、数据生成与反例构造的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 交换论证：理解交换论证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第8章｜在线算法、并行与验证（第2段）

理解本章在线算法、并行与验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 势能分析：理解势能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 斜率优化条件：理解斜率优化条件的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 四边形不等式：理解四边形不等式的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 分治优化递推：理解分治优化递推的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 最大流最小割定理：理解最大流最小割定理的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 强连通分量：理解强连通分量的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第9章｜在线算法、并行与验证（第3段）

理解本章在线算法、并行与验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 割点与桥：理解割点与桥的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 前缀函数：理解前缀函数的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. AC 自动机的失配指针：理解AC 自动机的失配指针的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 后缀数组的 LCP：理解后缀数组的 LCP的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 后缀自动机：理解后缀自动机的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 字符串哈希的碰撞：理解字符串哈希的碰撞的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第10章｜在线算法、并行与验证（第4段）

理解本章在线算法、并行与验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 期望复杂度分析：理解期望复杂度分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 布隆过滤器的误判率：理解布隆过滤器的误判率的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 概率数据结构：理解概率数据结构的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 近似比：理解近似比的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. NP 完全：理解NP 完全的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 在线算法的竞争比：理解在线算法的竞争比的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第11章｜在线算法、并行与验证（第5段）

理解本章在线算法、并行与验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 缓存竞争分析：理解缓存竞争分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 工作深度模型：理解工作深度模型的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 外存 I/O 复杂度：理解外存 I/O 复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 算法验证：理解算法验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 线段相交：理解线段相交的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 凸包的极角排序：理解凸包的极角排序的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
7. 旋转卡壳：理解旋转卡壳的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
8. 分治与平面细分：理解分治与平面细分的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

阅读边界

本页是学习路线和专题入口，不替代专题笔记中的机制解释、可运行示例和练习。笔记尚未完成的专题会先显示为占位页；已有经验的读者可以跳到具体章节，再按前置关系回补。

路线状态

本路线的目录已完成本轮架构审查；专题笔记的内容质量和来源审查另行进行。