以下按主题分组梳理常见算法与必备知识，便于快速索引与系统复习。
核心概念
- 复杂度分析: 时间/空间、摊还；渐进符号 O/Θ/Ω；常见 O(1)/O(log n)/O(n log n)。
- 递推与主定理: 分治类递归复杂度估计与解法选择。
- 正确性证明: 不变式、数学归纳、反证；贪心的交换论证/割性质。
- 随机化与概率: 随机快速选择/快速排序、哈希冲突的期望分析。
公式速查
复杂度定义（渐进符号）：
$$ f(n) = O(g(n)) \iff \exists c, n_0 > 0,\ \forall n \ge n_0,\ 0 \le f(n) \le c,g(n) $$
$$ f(n) = \Omega(g(n)) \iff \exists c, n_0 > 0,\ \forall n \ge n_0,\ 0 \le c,g(n) \le f(n) $$
$$ f(n) = \Theta(g(n)) \iff f(n)=O(g(n))\ \text{且}\ f(n)=\Omega(g(n)) $$
分治递推（主定理常见形态）：
$$ T(n)=a,T\left(\frac{n}{b}\right)+f(n),\quad a\ge1,\ b>1 $$
- 若 $f(n)=O\left(n^{\log_b a-\varepsilon}\right)$，则 $T(n)=\Theta\left(n^{\log_b a}\right)$。
- 若 $f(n)=\Theta\left(n^{\log_b a}\log^k n\right)$，则 $T(n)=\Theta\left(n^{\log_b a}\log^{k+1} n\right)$。
- 若 $f(n)=\Omega\left(n^{\log_b a+\varepsilon}\right)$ 且满足正则条件，则 $T(n)=\Theta(f(n))$。
摊还分析（动态数组扩容，倍增策略）：
$$ \mathrm{总成本}\ \sum_{i=1}^{m} c_i = O(m)\quad\Rightarrow\quad \mathrm{均摊插入} = O(1) $$
哈希负载因子与期望代价（拉链法）：
$$ \alpha = \frac{n}{m},\quad E[\text{链长}] = \alpha, $$
$$ E[\text{查找}]\approx O(1+\alpha) $$
生日悖论近似（冲突概率）：当哈希空间大小为 $M$，插入 $k$ 个键时，
$$ P(\text{至少一次冲突}) \approx 1 - e^{-\frac{k(k-1)}{2M}} $$
数据结构
- 线性结构: 数组、链表、栈、队列、双端队列。
- 哈希结构: 集合/映射、开放定址/拉链法、布隆过滤器。
- 堆与优先队列: 二叉堆、d 叉堆、斐波那契堆（理论）。
- 树结构: BST、AVL/红黑树(通过旋转和染色保持相对平衡）、Trie（前缀树）、线段树、树状数组（Fenwick）/跳表
- 并查集: 合并-查找，按秩合并 + 路径压缩。
线性结构：数组 vs 链表
数组强调连续内存与随机访问；链表强调节点插删灵活性。
栈与队列：同样是线性容器，不同是约束
- 栈：后进先出（LIFO）
- 队列：先进先出（FIFO）
哈希结构：冲突处理思想
冲突并不罕见，关键是冲突后如何组织数据。
树与堆：层级结构与局部有序
BST 关注“搜索顺序”，堆关注“堆序性质”。
并查集：合并集合 + 路径压缩
并查集维护“元素属于哪个连通分量”。
算法范式
- 分治: 归并排序、快速排序、最近点对。
- 动态规划: 状态设计、转移、路径还原；子序列/背包/区间/树形/状压。
- 贪心: 区间调度、哈夫曼编码、活动选择；需可证的贪心选择性质。
- 回溯与剪枝: 组合/排列/子集、N 皇后、数独；分支限界。
- 双指针与滑动窗口: 最长子串、最短覆盖、和为定值子数组。
- 前缀与差分: 前缀和/积、二维前缀、差分与区间更新。
- 二分（答案/位置）: 单调性判定 + 检验函数。
- Meet-in-the-middle: 折半搜索、子集和等。
图论
图的表示方式：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。
- 遍历与连通: BFS/DFS、拓扑排序、连通分量/强连通分量（SCC）。
- 环检测: 有向图用 Kahn（拓扑排序）或 DFS 三色标记；无向图用并查集或度数剪枝。
- 割点与桥: Tarjan 算法（基于 DFS 的 dfn/low 判定）。
- 最短路: Dijkstra、Bellman–Ford、SPFA、Floyd–Warshall。
- 最小生成树: Kruskal（并查集）、Prim。
- 拓扑与 DAG: 拓扑排序、DAG DP、关键路径。
- 流与匹配: 最大流（Edmonds–Karp/Dinic）、二分图匹配（Hungarian/Hopcroft–Karp）。
环检测
| 图类型 | 方法 | 核心逻辑 |
|---|---|---|
| 有向图 | Kahn 算法（入度） | 反复剔除入度为 0 的节点，若剩余节点则存在环 |
| 有向图 | DFS 三色染色 | 白→灰→黑，DFS 中遇到灰色节点即判定有环 |
| 无向图 | 度数剪枝（剥洋葱） | 反复剔除度数 ≤ 1 的节点，剩余度数 ≥ 2 的节点组成环 |
| 无向图 | 并查集 | 遍历边 (u, v)，若 u, v 已在同一集合则闭合有环 |
割点与桥
割点（Cut Vertex / Articulation Point）和桥（Bridge / Cut Edge）衡量无向图的连通脆弱性。
| 概念 | 定义 | 比喻 |
|---|---|---|
| 割点 | 移除后图分裂 | 交通核心枢纽瘫痪导致断联 |
| 桥 | 移除后图分裂 | 独木桥一断彻底隔绝 |
核心规律
- 桥不可能在环上（环上有替代路径）。
- 有割点不一定有桥；有桥通常意味着有割点（若桥边端点度数 ≥ 2，则为割点）。
Tarjan 算法判定（DFS + dfn/low）
| 类型 | 判定条件 | 直觉 |
|---|---|---|
| 割点 | low[v] >= dfn[u] | 子节点最多绕回 u 自身，断开 u 后子树孤立 |
| 桥 | low[v] > dfn[u] | 子节点连 u 都绕不回来，断边即失联 |
注：若 u 是 DFS 根节点，割点判定改为「有 ≥ 2 个独立子节点」。
应用场景: 网络容灾（单点故障检测）、社交网络分析（连接不同圈子的关键人物）。
字符串
- 模式匹配: KMP、Z-algorithm、Boyer–Moore、Rabin–Karp（滚动哈希）。
- 字典结构: Trie、Aho–Corasick（多模式）。
- 后缀结构: 后缀数组/树、LCP、后缀自动机。
- 其他经典: Manacher（回文）、最小表示法。
数论与计算几何
- 基础数论: GCD/扩展欧几里得、快速幂、模逆、CRT、筛法。
- 快速变换: FFT/NTT、多项式卷积、子集/莫比乌斯变换（进阶）。
- 计算几何: 叉积/方向判断、凸包（Graham/Andrew）、扫描线、线段相交、最近点对。
DP 优化（进阶）
- 单调队列优化、斜率优化（Convex Hull Trick）、分治优化、Knuth 优化、四边形不等式。
实用模式与选型
- 建模与归约: 归约到图/匹配/流/区间/背包等标准模型。
- 不变式与单调性: 为二分/贪心/单调队列提供充分条件。
- 规模估算经验: n≤1e5 常用 O(n log n)；n≤1e3 可用 O(n^3)；指数/状压配合小规模。
解题
判断一个问题该用什么算法，关键不是“背模板”，而是先做特征识别：从题目目标、数据范围、结构信号三条线索快速缩小候选算法。
看问法：题目到底要什么
题目目标通常直接对应算法类别：
| 题目目标 | 对应算法信号 | 常用算法/数据结构 |
|---|---|---|
| 最短路径/最少步数 | 图论或层级遍历 | BFS（广度优先）、Dijkstra |
| 所有组合/所有排列 | 搜索全部可能性 | 回溯（Backtracking） |
| 最大/最小、最多/最少 | 最优子结构 | 动态规划（DP）、贪心 |
| 是否包含/是否存在 | 查找与集合 | 哈希表、二分查找 |
| 区间求和/区间更新 | 数据维护 | 前缀和、线段树、树状数组 |
看规模：先用复杂度反推算法
根据输入规模 $n$ 先估算可接受复杂度，再选解法：
- $n \le 20$：常见回溯或状态压缩 DP（$O(2^n)$ / $O(n!)$）。
- $n \le 10^3$：常见 $O(n^2)$ 方案，如基础 DP、双层枚举。
- $n \le 10^5$：通常要 $O(n \log n)$ 或 $O(n)$，优先排序、堆、单调栈、双指针。
- $n \le 10^9$：通常需要 $O(\log n)$，常见于二分或数值方法。
看信号：常见题型触发器
- 有序数组：优先想到二分查找或双指针。
- 连续子串/子数组：优先想到滑动窗口。
- 树/图遍历：优先在 DFS 与 BFS 之间做选择。
- 局部最优推全局最优：先试贪心；若存在反例，转 DP。
DP 识别：两个硬条件
如果怀疑是 DP，至少检查：
- 重叠子问题：同一子结果会被重复使用。
- 无后效性：当前状态一旦确定，后续决策不依赖“到达路径细节”。
从套路到直觉
“信号触发器”是指南针，但高难题往往是多算法组合：
- 可能先 DFS 枚举，再用 DP 去重，最后用位运算压缩状态。
- 若某思路卡住（如 DP 维度过高），要立刻换建模或补数据结构（堆、线段树、并查集等）。
这套方法最大的价值，是快速排除错误方向：
- 大数据规模下立刻放弃暴力。
- 连续区间问题优先滑动窗口/前缀和，而不是盲目分治。
实战流程（新题通用）
- 手动模拟：先用小样例推演，找规律与边界。
- 检查单调性：有单调关系就考虑二分/双指针。
- 检查重复性：有重复子问题就考虑记忆化/DP。
- 检查贪心性：局部最优是否可证导出全局最优。
算法题与工程问题
现实问题通常先“摸索定义”，再“建模求解”，和算法题的路径不同：
| 维度 | 算法题（练习） | 现实问题（工程） |
|---|---|---|
| 条件 | 条件完整明确 | 条件可能缺失且有噪声 |
| 目标 | 单一目标，偏最优解 | 多目标权衡（性能/成本/维护性） |
| 过程 | 识别模型 -> 实现代码 | 定义问题 -> 建立模型 -> 迭代优化 |
为什么还要练算法题：
- 建立性能边界感，避免写出明显超时方案。
- 形成“可复用思维积木”，减少无效摸索。
- 先有保底可行解，再做工程化权衡和优化。
学习路径建议
数据结构建议顺序：
- 字符串、数组（重点：双指针、滑动窗口）
- 链表、栈、队列
- 二叉树（遍历、递归）
- 哈希表、集合
算法专题建议顺序：
- 贪心、排序
- 二分查找、回溯
- 动态规划（一维）
- 动态规划（多维）
- 图论
最后，刷题一定配合独立思考：先记录自己的尝试和卡点，再看题解反推思维误区。长期看，错误复盘比单纯刷题更能提升上限。