外观
算法核心原理与工程实践
快速查阅:本专题速记手册,包含知识点、排查顺序与工具参数。
面向中高级后端工程师,从业务约束出发,建立可证明、可验证、可观测的算法决策能力。
主线:现象与约束 → 问题建模 → 原理与证明 → 正确实现 → 测试与基准 → 故障定位 → 工程取舍。
本专题不以记忆题型模板为目标。读完后,应能回答三个问题:为什么这个算法正确、它在真实数据规模下是否可行、上线后如何证明性能问题确实来自这里。
建议学习路径
本专题不建议只按文件编号一路读到底。编号保留知识组织顺序,实际学习可按任务选择路径。
- 方法与验证:01 → 02 → A → 06 → 08
- 线性结构与局部状态:03 → 04 → 05 → 07 → 09 → 10
- 递归、树与搜索空间:11 → 13 → 14 → 12 → 15
- 图与依赖关系:17 → 16 → 18 → 19
- 优化问题:20 → 21 → 22 → 23 → 25
- 后端工程算法:04 → 26 → 27 → 28
| 路径 | 学完后应能回答的问题 |
|---|---|
| 方法与验证 | 输入规模如何决定方案,正确性和性能结论分别如何验证? |
| 线性结构与局部状态 | 如何利用访问顺序、局部状态和候选淘汰降低重复工作? |
| 递归、树与搜索空间 | 如何控制深度、重复访问、状态撤销和搜索空间爆炸? |
| 图与依赖关系 | 连通、依赖顺序和最低成本分别对应什么模型? |
| 优化问题 | 贪心、动态规划和状态压缩的成立条件分别是什么? |
| 后端工程算法 | 概率结构、流量控制和数据路由如何进入生产系统? |
A 是全专题通用的验证方法,应在深入具体算法前阅读,并在后续代码实践中反复使用。
文章定位
方法与基础结构
| 编号 | 主题 | 核心定位 |
|---|---|---|
| 01 | 时间复杂度如何决定系统上限 | 从线上数据规模推导算法容量上限,区分增长趋势与实测耗时 |
| 02 | 如何把业务问题抽象成算法模型 | 明确输入、约束、目标和不变量,避免按关键词套模板 |
| A | 算法正确性、测试与基准方法 | 用不变量、暴力基线、差分测试和 JMH 验证算法结论 |
| 03 | 数组与链表的真实取舍 | 结合定位成本、内存布局和修改模式选择线性结构 |
| 04 | Hash 表原理与工程应用 | 理解冲突、扩容、Key 契约以及 Hash 结构的能力边界 |
| 05 | 栈与队列的解题模型 | 用 LIFO、FIFO 和单调结构表达处理顺序 |
| 06 | 二分查找与答案搜索 | 用区间不变量在单调空间中搜索边界 |
| 07 | 双指针与滑动窗口 | 用单向移动和可增量维护状态消除重复扫描 |
排序、选择与区间
| 编号 | 主题 | 核心定位 |
|---|---|---|
| 08 | 排序算法怎么选 | 从稳定性、最坏情况、空间与数据分布选择排序方案 |
| 09 | Top K 与堆 | 只维护仍可能进入答案的候选集合 |
| 10 | 区间问题统一解法 | 统一端点语义,用排序、扫描线和堆处理区间关系 |
递归、树与搜索空间
| 编号 | 主题 | 核心定位 |
|---|---|---|
| 11 | 递归、调用栈与问题缩减 | 证明递归终止并控制调用栈风险 |
| 12 | 回溯算法与剪枝 | 在决策树中维护、撤销状态,并证明剪枝安全性 |
| 13 | 二叉树遍历与层级结构 | 根据节点处理时机选择 DFS、BFS 与迭代实现 |
| 14 | 二叉搜索树与有序索引 | 理解树高、范围查询、退化和平衡需求 |
| 15 | Trie 前缀树 | 以空间换取前缀定位能力,并处理字符集和内存边界 |
图与关系网络
| 编号 | 主题 | 核心定位 |
|---|---|---|
| 16 | 并查集与增量连通性 | 高效维护只增加连接的集合合并问题,不负责通用删边 |
| 17 | 图的 DFS 与 BFS | 处理重复访问、连通分量和无权最短路径 |
| 18 | 拓扑排序与依赖编排 | 生成 DAG 合法顺序并发现循环依赖 |
| 19 | 最短路径算法 | 根据边权条件选择 BFS、Dijkstra 或 Bellman-Ford |
贪心、动态规划与状态表达
| 编号 | 主题 | 核心定位 |
|---|---|---|
| 20 | 贪心算法与正确性证明 | 用交换论证等方法证明局部选择不会排除全局最优 |
| 21 | 动态规划的状态与转移 | 为重复子问题定义状态、依赖顺序和初始化 |
| 22 | 背包问题与资源分配 | 理解容量状态、遍历方向与伪多项式复杂度 |
| 23 | 序列动态规划 | 区分子串、子数组和子序列,并恢复实际方案 |
| 25 | 位运算与状态压缩 | 紧凑表达有限状态,并明确位宽和指数状态空间 |
字符串与后端工程算法
| 编号 | 主题 | 核心定位 |
|---|---|---|
| 24 | 字符串匹配与 KMP | 复用模式串前缀信息,避免文本回退 |
| 26 | Bloom Filter 与概率判断 | 用可计算的假阳性换取海量集合的空间效率 |
| 27 | 限流算法实战 | 比较速率控制算法;分布式部署与治理进入分布式专题 |
| 28 | 一致性哈希与缓存扩缩容 | 减少成员变化时的路由迁移;热点与副本需另行治理 |
阅读与验证约定
- 示例以 Java 17 为主;涉及 JDK 集合内部实现时,必须以目标 JDK 文档和源码为准。
- 先定义输入、输出、约束和不变量,再讨论代码模板。
- 正确性优先使用证明、暴力基线或差分测试验证;几个手工样例不能代替证明。
- 性能结论必须同时给出复杂度、数据规模、数据分布和运行环境;微基准优先使用 JMH。
- “平均
O(1)”“接近常数”“期望迁移比例”等结论必须保留成立条件。 - 工程案例要区分算法本身与生产协议:并发、持久化、发布、一致性和故障恢复通常不由单个算法自动提供。
- 文章中的“容易踩坑”用于预防;涉及生产故障时,还应给出症状、证据、定位步骤和修复验证。