| 算法思想 | 代表算法 | 时间复杂度 | 空间复杂度 | 关键字 / 特点 |
|---|
| 分治法 | 二分查找 | O(log n) | O(1) / O(log n) | 一分为二，减半查找 |
| 归并排序 | O(n log n) | O(n) | 拆分合并，稳定排序 |
| 快速排序 | O(n log n) 平均 / O(n²) 最坏 | O(log n) | 枢轴划分，非稳定 |
| 堆排序 | O(n log n) | O(1) | 完全二叉堆，原地排序 |
| 大整数乘法 (Karatsuba) | O(n^1.585) | O(n) | 分块相乘，比 O(n²) 快 |
| 矩阵乘法 (Strassen) | O(n^2.81) | O(n²) | 分块递归，优于 O(n³) |
| 汉诺塔 | O(2^n) | O(n) | 递归分解，移盘子 |
| 最近点对问题 | O(n log n) | O(n) | 平面点集，分治+合并 |
| 棋盘覆盖问题 | O(n²) | O(n²) | 缺角棋盘，分治填充 |
| | | | |
| 回溯法 | 八皇后问题 | O(n!) | O(n) | 解空间树，逐步试探 |
| 图的 m 着色问题 | O(m^n) | O(n) | 染色合法性，DFS 枚举 |
| Hamilton 回路 | O(n!) | O(n) | 访问一笔画，回路判定 |
| 旅行商问题 (TSP) | O(n!) | O(n) | 最短环路，指数级 |
| 子集和问题 | O(2^n) | O(n) | 枚举子集，判断和 |
| 数独求解 | 指数级 | O(n²) | 搜索解空间，强剪枝 |
| 迷宫求解 | 指数级 | O(n²) | 路径搜索，回头退栈 |
| 动态规划 | 斐波那契数列 | O(n) | O(n) / O(1) | 最优子结构，递推 |
| 最长公共子序列 (LCS) | O(m·n) | O(m·n)/O(min(m,n)) | 表格法，子问题重叠 |
| 最长公共子串 | O(m·n) | O(m·n) | 连续匹配，动态表格 |
| 背包问题 (0-1/完全/多重) | O(n·W) | O(n·W)/O(W) | 状态转移，容量约束 |
| 最长上升子序列 (LIS) | O(n²) 或 O(n log n) | O(n) | 子序列 DP，二分优化 |
| 矩阵链乘法 | O(n³) | O(n²) | 括号化顺序，区间 DP |
| 最优二叉搜索树 | O(n²) | O(n²) | 动态选择，代价最小 |
| Floyd-Warshall | O(n³) | O(n²) | 全源最短路，三重循环 |
| Bellman-Ford | O(VE) | O(V) | 松弛操作，可负权 |
| 编辑距离 | O(m·n) | O(m·n) | 插删改，字符串匹配 |
| 贪心法 | 活动选择 | O(n log n) | O(1) | 按结束时间排序，逐次选择 |
| 最小生成树 (Kruskal) | O(E log V) | O(V+E) | 边排序 + 并查集 |
| 最小生成树 (Prim) | O(E + V log V) | O(V+E) | 顶点扩展，堆优化 |
| 哈夫曼编码 | O(n log n) | O(n) | 频率最小合并，最优前缀码 |
| 分数背包 | O(n log n) | O(1) | 按单位价值排序，取部分 |
| 区间调度问题 | O(n log n) | O(1) | 区间选择，局部最优 |
| 单源最短路径 (Dijkstra) | O(E log V) | O(V+E) | 贪心扩展，非负权 |
| 多机调度问题 | O(n log n) | O(1) | 按任务长短/机器负载分配 |
| 找零问题 | O(n) | O(1) | 局部最优，贪心取币 |
$O(1) < O(log_2 n) < O(n) < O(nlog_2n) < O(n^2) < O(n^a) < O(2^a) $
| 类别 | 经典问题 | 时间复杂度 | 关键词/特点 |
|---|
| 基础 | 斐波那契数列 | O(n) | 最优子结构，递推 |
| 基础 | 切杆问题 | O(n²) | 分割切割，利润最大 |
| 序列 | 最长公共子序列 (LCS) | O(m·n) | 表格法，子问题重叠 |
| 序列 | 最长公共子串 | O(m·n) | 连续匹配 |
| 序列 | 最长上升子序列 (LIS) | O(n²)/O(n log n) | 子序列 DP，二分优化 |
| 序列 | 编辑距离 (202111) | O(m·n) | 插删改匹配 |
| 序列 | 最长回文子序列 | O(n²) | 区间DP，对称性 |
| 序列 | 最长回文子串 | O(n²) | 子串回文 |
| 序列 | 正则/通配符匹配 | O(m·n) | 模式匹配 |
| 背包 | 0-1 背包 | O(n·W) | 容量约束，取或不取 |
| 背包 | 完全背包 | O(n·W) | 物品可重复 |
| 背包 | 多重背包 | O(n·W) | 物品数量有限 |
| 背包 | 分组背包 | O(n·W) | 组内最多选1 |
| 背包 | 硬币找零 | O(n·amount) | 组合/兑换问题 |
| 区间 | 矩阵链乘法 | O(n³) | 区间DP，括号化顺序 |
| 区间 | 石子合并 (文件合并) | O(n³) | 合并代价最小 |
| 区间 | 戳气球 | O(n³) | 复杂区间DP |
| 区间 | 最优二叉搜索树 | O(n²) | 构造最优树 |
| 路径 | 最小路径和 | O(m·n) | 二维累加，网格DP |
| 路径 | 不同路径数 | O(m·n) | 组合数/路径数 |
| 路径 | 三角形最小路径和 | O(n²) | 自底向上 DP |
| 路径 | Floyd-Warshall | O(n³) | 全源最短路 |
| 路径 | Bellman-Ford | O(VE) | 单源最短路，可负权 |
| 博弈/特殊 | 蛋掉落问题 | O(n·k) | 最坏情况优化 |
| 博弈/特殊 | 最大子数组和 (Kadane) | O(n) | 连续子数组最大和 |
| 博弈/特殊 | 加权区间调度 | O(n log n) | 区间选择+权重 |
| 博弈/特殊 | Nim 游戏（DP 变种） | O(n·状态) | 博弈状态转移 |
- 暴力递归
- 定义：直接根据
F(n) = F(n-1) + F(n-2) 递归求解
- 复杂度：O(2^n)
- 特点：有大量重复子问题，不是严格意义上的分治（因为分治强调“子问题不重叠”）。
- 动态规划
- 自顶向下（记忆化搜索）
- 自底向上（迭代表格法）
- 复杂度：O(n)，空间可优化到 O(1)
- 特点：保存子问题结果，避免重复计算。
- 高效解法
- 矩阵快速幂：O(log n)
- 通项公式（Binet 公式）：O(1)（有精度问题）
- O(2^n) 解法：应该称为暴力递归，而不是“分治法”。
- 分治法：虽然名字上也用递归，但核心要求是“子问题互不重叠”，而斐波那契递归是重叠子问题的典型 → 所以严格来说它是 DP 的反例，不是“分治”。
- O(n) 解法：才是 动态规划 的正宗体现。
- 0-1背包问题 200911
- 最大字符匹配对数 202811
- 切杆问题 201805
- 最长公共子串 201511
- 矩阵链乘法 201311
- 编辑距离定义DNA序列 202111