核心算法
面试必考算法原理详解：排序、搜索、递归、动态规划。
本章节包含
| 算法 | 核心思想 | 面试重点 |
|---|---|---|
| 排序 | 比较、分治、计数 | 快排、归并、堆排序、稳定性 |
| 搜索 | 减治、遍历 | 二分查找、DFS、BFS |
| 递归与分治 | 自相似分解 | 递归树、尾递归、主定理 |
| 动态规划 | 最优子结构 | 状态定义、转移方程、空间优化 |
| 贪心 | 局部最优 | 与 DP 的区别、适用条件 |
| 复杂度分析 | 数学估算 | 主定理、摊还分析 |
| 图论 | 图遍历与优化 | 拓扑排序、最短路径、MST、并查集 |
| 高级数据结构 | 区间查询与修改 | 线段树、树状数组、Lazy Propagation |
| DP 套路模板 | 套路分类与模板代码 | 线性/区间/背包/树形/状压五类模板与优化 |
| 图论模板 | 模板速用 | BFS/DFS、Dijkstra、拓扑排序、并查集、MST |
算法选型速查
| 场景 | 推荐算法 | 时间复杂度 |
|---|---|---|
| 通用快速排序 | 快速排序 | O(n log n) 平均 |
| 需要稳定性 | 归并排序 | O(n log n) 稳定 |
| 数据范围小 | 计数排序 | O(n + k) |
| 海量数据 Top K | 堆排序 / 快速选择 | O(n log k) / O(n) |
| 查找有序数组 | 二分查找 | O(log n) |
| 图遍历 | DFS / BFS | O(V + E) |
| 最短路径（无负权） | Dijkstra | O((V + E) log V) |
| 最短路径（有负权） | Bellman-Ford | O(V * E) |
| 最小生成树 | Kruskal / Prim | O(E log E) / O((V + E) log V) |
| 连通性/环检测 | Union-Find | O(α(N)) |
| 拓扑排序 | Kahn / DFS | O(V + E) |
| 区间和 + 单点修改 | 树状数组（BIT） | O(log n) |
| 区间修改 + 区间查询 | Lazy 线段树 | O(log n) |
| 逆序对计数 | BIT + 离散化 | O(n log n) |
| 最优子结构问题 | 动态规划 | 视问题而定 |
每个子章节包含：原理、代码实现、复杂度证明、面试真题。