1 · 读书笔记：图解算法

1.1 · 核心观点：

1. 使用Big O去分析时间/空间复杂度：常量、线性、对数
2. 基本数据结构：数组（连续空间）、链表（非连续空间）；两者的优缺点
3. 散列表：散列函数、冲突（开放地址、链地址法）、填装因子
4. 图：深度、广度；拓展（加权最短路径、K近邻用于分类回归）
5. 树：前序、中序、后序
6. 范式（战略）：分而治之、贪婪、动态规划
7. 实现（战术）：迭代loop、递归recursive(每一次递归一个栈帧：基线条件（结束）、递归条件)

细说范式：

• 分而治之：快速排序 O(n log n)
• 贪婪：每一步采取最优解，从而得到接近最优解；
• 动态规划DP：先解决子问题，再逐步解决大问题；通过合并子问题的解得到更大问题的解；

一些应用：

• 布隆过滤器：散列+位数组
• MapReduce：分布式下任务的分而治之

1.2 · 启发点（关键洞察）：

1. 选对数据结构比优化算法更重要：很多性能问题不是算法慢，而是数据结构选错了。散列表 O(1) 查找 vs 数组 O(n) 遍历，差距是结构性的。
2. 递归的核心不是”自己调自己”，而是把问题缩小到基线条件：理解递归的关键是看清每一步如何把问题规模减一，而不是试图在脑中展开整个调用栈。
3. 贪婪算法的价值在于”足够好”：很多 NP 完全问题没有多项式时间精确解，贪婪给出的近似解在实际中往往足够用，关键是识别问题是否属于这一类。
4. 动态规划的本质是”记住子问题的答案”：和分治的区别在于子问题有重叠；DP 通过缓存避免重复计算，把指数级降到多项式级。
5. Big O 不是精确计时器，而是增长趋势的表达：它告诉你”数据量翻倍时，时间会怎么变”，帮你在 n 还小的时候就预判 n 变大后的问题。

1.3 · 行动：

1. 遇到性能问题时，先检查数据结构是否匹配访问模式（查找用散列表、有序遍历用排序数组/树），再考虑算法优化。
2. 写递归前先明确写出基线条件和递归条件，确保问题规模每步都在缩小。
3. 面对复杂优化问题时，先判断是否 NP 完全；如果是，直接考虑贪婪或近似算法，不要浪费时间找精确解。

1.4 · 金句：

1. “An algorithm is a set of instructions for accomplishing a task.” — Aditya Bhargava
2. “O(log n) is faster than O(n), but it gets a lot faster once the list of items you’re searching through grows.” — Aditya Bhargava
3. “You can’t access random elements in a linked list… With arrays, you know the address for every element.” — Aditya Bhargava