1 · 读书笔记：图解算法

Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People

https://book.douban.com/subject/26979890/

• 是什么（What）— 理论/原则，建立认知模型
• 为什么（Why）— 背后的动机、约束与权衡
• 怎么做（How）— 技巧 + 实践 + 边界（该做与不该做）

1.1 · 核心观点：

算法不是越快越好的咒语，而是在给定问题上，理解数据结构选择比算法优化更影响性能。Big O 不是精确计时器，而是帮助程序员在数据规模变大时做出正确决策的思维工具。同一问题的解法往往有多个，关键是识别问题的结构，选择最匹配的范式（分治、贪婪、动态规划）。

1.1.1 · 关键内容：

1. 数据结构选择是性能的首要因素：数组 vs 链表、散列表 vs 排序数组，选错可能导致量级差异（O(1) vs O(n)）
2. Big O 分析三层：常量时间（O(1)）、线性（O(n)）、对数（O(log n)）、线性对数（O(n log n)）、平方（O(n²)）
3. 基本数据结构：数组（连续空间，快速随机访问但插入删除慢）、链表（非连续，插入删除快但访问慢）
4. 散列表：散列函数、冲突处理（开放地址法、链地址法）、装填因子
5. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）；最短路径（Dijkstra）、最小生成树
6. 算法范式（战略级）：
   • 分而治之（Divide & Conquer）：快速排序、归并排序 O(n log n)
   • 贪心算法（Greedy）：每步采取局部最优，适合 NP 完全问题的近似解
   • 动态规划（DP）：子问题有重叠时，缓存避免重复计算
7. 实现范式（战术级）：递归 vs 迭代，递归清晰但占栈空间，迭代高效但代码复杂

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