Module 03
第三阶段：核心算法
目标：理解算法为什么正确、状态如何变化、复杂度如何推导，而不是只背模板。
建议阅读顺序
- 排序算法 — 冒泡、选择、插入、希尔、归并、快排、堆排、计数、桶、基数
- 二分查找 — 区间定义、边界查找与二分答案
- 双指针 — 对撞、快慢、同向指针
- 滑动窗口 — 窗口状态、扩张与收缩
- 递归与回溯 — 决策树、选择与撤销
- DFS / BFS — 图和网格搜索、拓扑排序
- 动态规划 — 状态、转移、初始化与遍历顺序
- 贪心算法 — 局部选择与正确性依据
读算法题解的五个问题
- 输入规模决定允许什么复杂度？
- 状态变量分别代表什么？
- 每一步为什么不会漏解或重复？
- 循环不变量或递归定义是什么？
- 边界输入怎样处理？
从数据规模估计复杂度
| n 的大致范围 | 常见可接受复杂度 |
|---|---|
| n <= 20 | O(2^n)、O(n!) 的剪枝搜索 |
| n <= 500 | O(n²) |
| n <= 10^5 | O(n log n) 或 O(n) |
| n <= 10^6 | 接近 O(n) |
这是经验范围，还要考虑常数、语言和测试时限。
学完应该能做到
- 手写归并、随机快排、堆排和常见非比较排序。
- 统一处理二分查找边界。
- 从暴力解法识别可维护的窗口或 DP 状态。
- 在 DFS 与 BFS 之间根据问题目标做选择。
- 给出时间、空间复杂度以及正确性的关键理由。