算法基础与复杂度

这部分知识我前后看过不止一次。刚接触“算法基础与复杂度”时，我总想跳过复杂度和递归，直接去刷看起来更有成就感的题，结果越刷越依赖答案。等我回头从问题本身出发，而不是从模板出发，很多原来零散的规则才慢慢连在一起。下面按我自己的理解过程展开。

算法基础这一章不是“背模板”，而是先把算法的底层判断力建起来：一个问题规模有多大、能不能递归拆、递归树长什么样、数学性质能不能减少枚举。

如果这里不扎实，后面学二分、分治、回溯、动态规划、图论都会有一种感觉：代码能背下来，但换个题就不知道为什么这样写。

先用做饭理解“算法”

菜谱规定输入材料、处理步骤和最终结果，就是一种算法。两份菜谱都能做出同一道菜，但一份要反复洗锅、切菜，另一份会合并步骤；结果同样正确，成本却不同。程序里的复杂度，就是在估算数据变多后，步骤和额外空间会怎样增长。

递归像把“大份任务”交给几个更小的自己；分治要求这些小任务能够独立处理并合并；数学性质则帮助我们直接跳过大量没有必要的枚举。

我第一次读这一章时，只先要求自己会循环、数组和普通函数。不会证明复杂度也没关系，先学会数“关键操作大约执行多少次”。

我为什么先补这一章

这一章主要解决三个问题：

1. 看到题目时，先判断大概允许什么复杂度。
2. 遇到递归问题时，能画出递归树和调用栈。
3. 遇到数学约束时，能把公式安全地落成代码。

我自己的学习顺序

我后来按这个顺序重新学了一遍：

1. 算法复杂度与递归：先学会估成本和拆问题。
2. 分治算法：从递归树到合并结果。
3. 数学算法基础：取模、GCD、快速幂与素数筛。

我当时最容易混淆的地方

复杂度不是代码行数，而是输入规模增长时，操作次数怎么增长。

递归不是“函数调用自己”这么简单，真正要看的是：

• 子问题有没有变小。
• 终止条件是否完整。
• 每一层做了多少额外工作。
• 是否有重复子问题。

数学算法也不是为了炫技，它经常出现在哈希、加密、计数、随机、分布式 ID、限流和海量数据题里。

我后来这样检查自己是否真的理解

我学完这一章后，会用这些问题检查自己：

• 为什么 O(n log n) 通常比 O(n²) 更适合大规模排序？
• 递归爆栈通常是终止条件问题，还是递归深度问题？
• 分治和动态规划最大的区别是什么？
• 快速幂为什么能把幂运算从 O(n) 降到 O(log n)？