# 《算法图解》知识点全解

> AI生成｜2026年10月29日｜codebuddy｜原书：巴尔加瓦《算法图解》，人民邮电出版社，2017-03-01
> **我的阅读**：进度 100%｜累计 3小时22分钟｜开始 2018-12-06｜最近 2021-04-21｜读完 2018-12-10

**一句话总结**：这本书不教你推导证明，只训练一种判断力——面对一个具体问题，能说出「该用哪类算法、代价大概多少、边界在哪里、拿不到精确解时怎么办」。

**适合谁 / 前置知识**：适合有基础编程经验（会写循环、函数、列表）的在职程序员、计算机专业低年级学生、以及想补「算法直觉」而非「竞赛技巧」的自学者；也适合产品/测试岗想理解「这个需求为什么慢」。不适合备战算法竞赛、或需要严格复杂度证明与工程实现细节的读者——那类需求应直接读《算法导论》层次的教材。前置只需一门语言的函数与列表操作，书中代码是 Python 风格，不熟 Python 也能读懂；不需要微积分和概率论。

## 一、全书地图

全书是三段递进：**建工具（1–4）→ 用工具（5–10）→ 看边界（11）**。第 1 章不是导论而是标尺，后面每章都在用它量代价。

| 章节 | 主题 | 核心产出 | 依赖 |
|---|---|---|---|
| 第1章 算法简介 | 二分查找、大O表示法 | 用增长率而非秒数比较算法 | — |
| 第2章 选择排序 | 内存工作原理、数组与链表 | 理解「随机访问 vs 增删」的取舍 | 大O |
| 第3章 递归 | 基线条件、递归条件、栈 | 会解释递归的空间代价 | — |
| 第4章 快速排序 | 分而治之、快排、再谈大O | 理解同一算法为何有两种复杂度 | 递归、大O |
| 第5章 散列表 | 散列函数、应用、冲突、性能 | 用字典把查找压到平均 O(1) | 数组 |
| 第6章 广度优先搜索 | 图、BFS、实现图与算法 | 无权图上的最短路径 | 散列表、队列 |
| 第7章 狄克斯特拉算法 | 加权图、术语、负权边、实现 | 加权图上的最短路 | 第6章 |
| 第8章 贪婪算法 | 教室调度、背包、集合覆盖、NP完全 | 识别「没有快解」并给近似 | 集合 |
| 第9章 动态规划 | 背包、FAQ、最长公共子串 | 用表格消掉重复子问题 | 网格思维 |
| 第10章 K最近邻 | 分类、推荐系统、机器学习简介 | 用邻居做预测 | 距离度量 |
| 第11章 接下来如何做 | 树、反向索引、傅里叶、并行、MapReduce、概率结构、SHA、线性规划 | 知道还有哪些工具可选 | 全书 |

两条隐藏主线：**「查找」从 O(n)→O(log n)→O(1)**（第1、5章），**「图」从无权到加权、从能走到最便宜**（第6、7章）。第8、9章是难问题的两条出路：近似与精确但受限。第10章从「计算」转向「预测」。

## 二、核心知识点

### 1. 二分查找
**是什么**：在有序序列上每次砍掉一半搜索区间，复杂度 O(log n)。
**为什么重要**：10 亿个元素，线性查找约 10 亿步，二分约 30 步。这是「算法选择能带来数量级差异」最干净的示范。
**怎么用**：维护 low/high 两个边界，取中点比较后移动边界，循环条件写 `low <= high`。猜数游戏、「这版代码是哪次提交引入的」都是同一模型。
**常见误区**：忘了前提是有序；中点写成 `(low+high)/2` 在超大整数下溢出（应为 `low+(high-low)/2`）；边界更新成 `low = mid` 导致死循环。

### 2. 大O表示法
**是什么**：描述最坏情况下运行时间随输入规模的增长速度，忽略常数与低阶项。
**为什么重要**：它让算法能脱离机器比较，也是容量规划与面试沟通的通用语言。
**怎么用**：数循环层数（嵌套相乘）；看每层规模是否减半（减半即 log）；排序关系 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n!)。
**常见误区**：把大O当精确耗时（常数极大的 O(n) 可能慢于小 n 的 O(n²)）；只看平均不看最坏；只算时间不算空间；把「合并两个循环」误判为 O(n²)。

### 3. 数组与链表
**是什么**：数组内存连续，随机访问 O(1)、中间插入删除 O(n)；链表节点分散存储并保存下一节点地址，插入删除 O(1)、访问 O(n)。
**为什么重要**：几乎所有数据结构都是这两者的变形与折中，选错会让热路径慢一个量级。
**怎么用**：读多写少、要下标 → 数组；频繁在头部/中间增删、长度不定 → 链表；拿不准时先用数组（缓存局部性好，实践中常更快）。
**常见误区**：以为「链表插入一定快」——定位插入点本身要 O(n)；以为数组删除只是置空（后续元素要移位）；忽略数组扩容时的整体复制成本。

### 4. 选择排序
**是什么**：每轮扫描剩余部分找最小值，追加到已排序区末尾，O(n²)。
**为什么重要**：教学价值大于实用价值，是「用嵌套循环换正确性」的最小样板，用来对照快排的 O(n log n)。
**怎么用**：外层 i 从 0 到 n-1，内层在 [i, n) 找最小索引后交换；适合 n 很小或只要求「选出前 k 个」的场景。
**常见误区**：以为它是 O(n log n)；忽略它不稳定（相同值相对次序会变）；在百万级数据上仍直接使用。

### 5. 递归、基线条件与调用栈
**是什么**：函数调用自身；必须同时有基线条件（何时停）与递归条件（如何把问题变小）。每次调用在调用栈上压一帧，帧内存局部变量。
**为什么重要**：递归是分治、树遍历、图搜索的表达基础；栈则解释了递归的内存代价、栈溢出与「为什么递归能记住回来的路」。
**怎么用**：先写基线（最简单、可直接返回的情形），再假设子问题已解，只写当前层的组合逻辑。写不出基线，说明问题还没想清。
**常见误区**：基线缺失或不可达导致无限递归；递归深度大时爆栈（改迭代或显式栈）；以为递归一定比循环慢（多数情况只是常数差异）；以为递归能自动「记住」结果（那需要记忆化）。

### 6. 分而治之（D&C）
**是什么**：把问题拆成同构的子问题，分别求解再合并，是递归的工程化方法论。
**为什么重要**：二分、快排、归并都是它的实例；它也是拆分业务需求、拆分大规模数据的通用思路。
**怎么用**：三步——找基线（最小可直接解的情形）、分解（规模变小但结构不变）、合并（子结果合成答案）。书中「把矩形地均匀分成最大方块」就是递归版的欧几里得算法。
**常见误区**：分解后子问题不同构，无法复用同一函数；忽略合并成本（合并 O(n) 时才可能整体 O(n log n)）；拆得比收益更细，管理开销反超计算收益。

### 7. 快速排序
**是什么**：选基准值 pivot，把数组分成小于/大于两部分，递归处理两侧；平均 O(n log n)，最坏 O(n²)。
**为什么重要**：实践中常快于归并（原地、常数小），也是「同一算法两种复杂度」的最佳教学案例，直接引出「随机化」这一工程手段。
**怎么用**：随机选基准或三数取中，避免有序输入退化；小数组切到插入排序；只需要前 k 大时改用选择/堆。
**常见误区**：固定取首元素作基准（已排序输入退化）；以为快排稳定（不稳定，要稳定用归并）；把「平均快」当成「任何输入都快」；忘记递归深度也是空间 O(log n)～O(n)。

### 8. 散列表
**是什么**：散列函数把键映射到桶，实现平均 O(1) 的查找、插入、删除；冲突用链表或开放寻址解决。
**为什么重要**：这是「空间换时间」最成功的结构，字典、集合、缓存、去重、图邻接表的底层都是它。
**怎么用**：四类典型用途——查找（电话簿、DNS 缓存）、防止重复（投票去重）、缓存（记住已算过的结果）、邻接表建图。填装因子（元素数/桶数）超过约 0.7 就扩容 rehash。
**常见误区**：以为查找永远 O(1)（最坏 O(n)，取决于散列质量与冲突处理）；用可变对象当键；依赖字典的遍历顺序；把普通散列当加密（可碰撞、可枚举，安全场景要用加盐慢散列）。

### 9. 图与广度优先搜索（BFS）
**是什么**：图由节点与边组成（有向/无向）；BFS 用队列按「跳数」逐层扩展，在无权图上给出最短路径（最少边数）。
**为什么重要**：社交关系、路由、依赖解析、状态空间搜索都是图问题；「最短」在无权图上就等于「最少步数」。
**怎么用**：队列存待查节点，散列表记已访问；入队时就标记 visited 以防重复；运行时间 O(V+E)。例：在人际关系网中找「最近的芒果经销商」。
**常见误区**：不加 visited 导致循环或指数级重复；用栈代替队列（退化为 DFS，不再保证最短）；在有边权的图上直接套 BFS 求「最便宜」路径；把「最短路径」误解为「权重最小」。

### 10. 狄克斯特拉算法
**是什么**：在非负权图上，每轮取当前距离最小的未处理节点，松弛其邻居；得到单源最短路径。
**为什么重要**：地图导航、成本最小化、网络选路的基线算法，也是「BFS 的加权版」这一谱系的关键一环。
**怎么用**：三张表——图（邻居及权重）、开销（到各点当前最小代价）、父节点（用于回溯路径），外加一个已处理集合。每轮找最小开销节点 → 更新邻居 → 标记已处理；最后沿父节点回溯出路径。
**常见误区**：用于含负权边的图（会给出错误结果，应改用贝尔曼-福特）；忘记「已处理节点不再更新」，导致反复回炉；无向图只加单向边；把「换钢琴」这类多跳折价问题当成算术题而没建图。

### 11. 贪婪算法与集合覆盖
**是什么**：每步只选当前看起来最优的解，不回溯；对集合覆盖这类问题给出近似解。
**为什么重要**：精确解不可行时的默认退路——快、简单、常有可证明的近似比。书中「广播台覆盖全美各州」就是典型：穷举 2^n 不可行，贪婪几轮就能得到接近最优的方案。
**怎么用**：集合覆盖——每轮选「覆盖最多尚未覆盖元素」的集合，直到全覆盖；教室调度——按最早结束时间排序依次选；背包——按单位价值排序（但这只是近似）。
**常见误区**：以为贪婪必得最优（0/1 背包会选错）；不评估近似比就上线；把「贪婪」理解成「随便选第一个」；忽略贪婪对输入顺序敏感。

### 12. NP完全问题
**是什么**：目前没有已知多项式时间解法、但给定解可在多项式时间验证的问题类（旅行商、集合覆盖、图着色等）。
**为什么重要**：识别它，才能在需求评审时及时说「要精确解不现实」，把方案改成近似、限规模或改约束，而不是硬算到超时。
**怎么用**：识别信号——元素组合爆炸、要求「覆盖全部/访问每个一次」、可归约到已知 NP 完全问题、规模稍大就算不动、换个近似条件就突然变简单。应对：近似算法、限制输入规模、启发式/分支限界。
**常见误区**：把「我不会做」当成 NP 完全；以为 NP 完全问题完全无解（小规模精确解仍可行）；把 NP 与「不可计算」混为一谈；以为近似解「不严谨」所以不能用。

### 13. 动态规划
**是什么**：把问题拆成重叠子问题，用表格自底向上记录每个状态的最优值，每格只算一次。
**为什么重要**：它是「精确解 + 可接受复杂度」的少数通用手段；背包、编辑距离、最长公共子串都是同一套模板。
**怎么用**：背包——行是物品、列是容量，每格取「不拿」与「拿（剩余容量 + 本件价值）」的较大值；最长公共子串——行是串 A、列是串 B，字符相同取左上角 +1，否则置 0；最长公共子序列则在不相等时取 max(上, 左)。
**常见误区**：把最长公共**子串**（连续）与**子序列**（可不连续）混为一谈；以为 DP 万能（需最优子结构与可离散状态）；只写转移方程不定义初始边界；以为 DP 能处理「只能整件拿」之外的连续取值（那需要线性规划）。

### 14. K 最近邻（KNN）
**是什么**：给新样本找特征空间中最近的 K 个已知样本，分类看多数票，回归取均值。
**为什么重要**：最简单的「从数据到预测」的桥梁，推荐系统、OCR、垃圾邮件过滤都能用它起步；也是理解「特征工程比模型更重要」的入口。
**怎么用**：选特征 → 归一化 → 选距离（欧氏用于连续特征，余弦用于偏好向量）→ 选 K（奇数，交叉验证）→ 投票或平均。书中橙子/柚子按「大小 + 颜色」两个特征分类，推荐系统按用户偏好向量的夹角找近邻。
**常见误区**：不做归一化（量纲大的特征主导距离）；K 取偶数导致平票；K 太小过拟合、太大欠拟合；样本量大时暴力算距离成本高（需 KD 树或近似检索）；把「邻居多」当成「置信度高」。

### 15. 单机之外的十件工具
**是什么**：树（层次数据；B 树做数据库索引）、反向索引（「词 → 文档」映射，搜索引擎核心）、傅里叶变换（把信号拆成频率成分）、并行算法（多核分摊，但有通信与串行上限）、MapReduce（map 分发 + reduce 汇总的分布式框架）、布隆过滤器（用位数组判断「可能存在/一定不存在」）、HyperLogLog（估算去重基数）、SHA 算法（单向散列，做完整性校验与存密码）、局部敏感散列（让相似项落到同一桶）、Diffie-Hellman（不传输密钥也能协商出共享密钥）、线性规划（在约束下优化目标，如用资源换利润最大化）。
**为什么重要**：这些决定了系统能否规模化，也是「单机 + 精确」之外现实世界的主力工具箱。
**怎么用**：按约束选——省空间且能容忍误判用布隆过滤器；估算 UV 用 HyperLogLog；查相似/去重近似用 LSH；多机聚合用 MapReduce；资源分配求最优用线性规划。
**常见误区**：用布隆过滤器判断「一定存在」（它只会误报存在，不会漏报）；用普通散列存密码（应加盐 + 慢散列）；以为加机器就一定线性变快（Amdahl 上限）；把 SHA 当加密（它是单向摘要，不可逆）。

## 三、关键概念速查表

| 概念 | 一句话解释 | 用在哪儿 |
|---|---|---|
| 二分查找 | 有序区间每次折半 | 有序数据检索、git bisect、猜数 |
| 大O表示法 | 忽略常数的增长率上界 | 算法选型、容量评估 |
| 数组 | 连续内存，随机访问 O(1) | 下标访问、缓存友好场景 |
| 链表 | 节点带指针，增删 O(1)、访问 O(n) | 队列、LRU、频繁增删 |
| 递归 | 函数自调用 + 基线条件 | 树/图遍历、分治 |
| 调用栈 | 每次调用压一帧 | 解释递归内存与栈溢出 |
| 分而治之 | 拆同构子问题再合并 | 快排、归并、批处理拆分 |
| 快速排序 | 选基准分区后递归，平均 O(n log n) | 通用排序、top-k 变体 |
| 散列函数 | 键 → 桶号的映射 | 字典、缓存、去重 |
| 冲突 | 不同键落到同一桶 | 选择链表法/开放寻址 |
| 填装因子 | 元素数 / 桶数，超阈值扩容 | 散列表性能调优 |
| 图 | 节点 + 边，可有权、有向 | 关系建模、依赖、路网 |
| 队列 | 先进先出 | BFS、任务缓冲 |
| 广度优先搜索 | 按跳数逐层扩展 | 无权图最短路径、最少步数 |
| 狄克斯特拉算法 | 每轮取最小开销节点并松弛 | 非负权最短路、导航 |
| 负权边 | 边权为负，破坏 Dijkstra 前提 | 改用贝尔曼-福特 |
| 贪婪算法 | 每步取局部最优不回溯 | 调度、覆盖、近似解 |
| 集合覆盖 | 用最少集合覆盖全集 | 选点投放、测试用例挑选 |
| NP完全问题 | 无已知多项式解，解可快速验证 | 判断「该不该放弃精确解」 |
| 动态规划 | 表格记录重叠子问题最优值 | 背包、编辑距离、LCS |
| 最长公共子串 | 两串中最长的连续公共片段 | diff、抄袭检测、相似度 |
| KNN | 看最近的 K 个邻居投票/取均值 | 分类、回归、推荐 |
| 特征归一化 | 把各维缩放到可比范围 | KNN、距离类模型必做 |
| 反向索引 | 词 → 包含它的文档列表 | 全文检索 |
| MapReduce | map 分发、reduce 汇总 | 大规模批处理 |
| 布隆过滤器 | 位数组 + 多哈希，可能误报不会漏报 | 缓存穿透防护、URL 去重 |
| HyperLogLog | 用少量内存估算基数 | UV 统计 |
| SHA | 单向散列，输入变则输出大变 | 校验、密码存储、去重 |
| 线性规划 | 约束下最大化/最小化目标函数 | 资源分配、排产 |

## 四、可复用的方法/框架

**4.1 选算法的五问（拿到需求先问，再动手）**
1. 数据规模多大？n 小于几百时，先写对的，别过度设计。
2. 数据有序/可排序吗？有序就该想到二分。
3. 问题类型是哪类：查找、排序、最短路、组合最优、分类预测？
4. 图有边权吗？有负权吗？有负权就别用 Dijkstra。
5. 需要精确解还是可接受近似？判定为 NP 完全就转近似或缩规模。

**4.2 复杂度估算四步**
看最深层循环 → 判断每层规模是否随 n 缩小（减半则 log）→ 相乘得主项 → 补上空间与最坏情况。写完再问一句「最坏输入长什么样」，能覆盖 80% 的性能事故。

**4.3 动态规划五步建模**
定义状态（格子代表什么）→ 写转移（当前格由哪些格推来）→ 定边界（第一行/列为 0 或其他基准）→ 定遍历顺序（保证依赖已算）→ 回溯答案（必要时记录选择）。

**4.4 NP 完全自检清单**
出现「全排列/组合爆炸」「每个都要访问一次」「覆盖所有需求」「规模翻倍时间爆炸」时，先假设它是 NP 完全，再去找近似方案与可接受的误差。

**4.5 学习闭环（本书的方法论本身）**
每章先看图 → 手推一个小例子 → 用 10 行代码实现 → 改一个边界条件看它坏在哪 → 一句话写清「它解决什么、代价多大」。这本书的价值不在读懂，而在能复述出「什么时候不该用它」。

## 五、我的阅读轨迹

| 项目 | 数据 |
|---|---|
| 进度 | 100% |
| 累计阅读 | 3小时22分钟 |
| 开始阅读 | 2018-12-06 |
| 最近阅读 | 2021-04-21 |
| 读完时间 | 2018-12-10 |

**复习建议**：全书已读完，但 3 小时 22 分钟对一本含 11 章 + 练习的书属于「快速通读」，且首读到读完仅 4 天（2018-12-06 → 12-10），最近一次翻动已是 2021-04，距今超过 5 年——当时的理解大概率只剩名词印象。建议按「高遗忘风险」优先复读：**第 9 章动态规划**（表格建模最易忘，且最需要动手画）、**第 7 章狄克斯特拉**（三张表 + 负权边界最容易记混）、**第 8 章 NP 完全**（判断清单不复习就不会用）、**第 4 章快排的平均/最坏**（概念清楚但容易说不清）。第 1、2、5 章属于长期记忆较牢的基础，可只做速查表自测。第 11 章是索引式内容，用的时候再查即可。

## 六、行动清单

1. 手写一遍二分查找，故意用 `low = mid` 制造死循环，再改对——把边界错误变成肌肉记忆。
2. 用自己项目里的一个真实查询，估算它的大O，并写下「n 翻 10 倍会怎样」。
3. 把一段递归代码改写为显式栈版本，对比两者的内存占用。
4. 给一个含负权的最短路场景跑一次 Dijkstra，亲眼看到错误结果，再换贝尔曼-福特。
5. 用动态规划表手算「容量 4、三件物品」的背包，把每一格的最优值与来源画出来。
6. 为 KNN 写一个「不归一化 vs 归一化」的对照实验，观察准确率差异。
7. 整理一份个人「NP 完全识别清单」，贴到需求评审用的文档里。
8. 用布隆过滤器给一个缓存加穿透保护，记录误判率与内存占用。

## 七、延伸阅读

1. **《算法（第4版）》，Sedgewick**——先读本书建立直觉，再读它补齐排序、查找、图算法的完整实现与性能分析。顺序：本书 → 这本，前者给「选什么」，后者给「怎么写对、为什么这样写」。
2. **《编程珠玑》，Bentley**——本书讲算法长什么样，这本讲「在真实约束下怎么把问题变小」。适合在读完第 8、9 章后读，能校准「近似与精确」的工程判断。
3. **《数据结构与算法分析》，Weiss**——本书刻意回避的严格证明与摊还分析，在这里补上；也可作为《算法导论》之前的过渡。顺序：本书 → Weiss → 需要时再查《算法导论》。