《算法图解》读书笔记（初学者精讲版）

《算法图解》（Grokking Algorithms），Aditya Bhargava 著，图灵程序设计丛书。200 页、400 多张手绘图，是公认最好的算法入门书。

这一篇不是摘要，而是把书里的核心知识按初学者路线重新讲一遍：每章都走”生活直觉 → 怎么做 → 代码 → 大 O”四步。原书代码是 Python 2.7 的老写法，本文全部用 Python 3 重写。建议边读边把代码敲一遍。

先建立一个问题意识：算法到底是什么

书里给的定义很简单：算法是一组完成任务的指令。任何代码片段都可以叫算法，但有意思的算法要么速度快，要么能解决有趣的问题。这本书要回答的其实只有两个问题：

1. 怎么把一件事做得更快？（二分查找比傻找快 3300 万倍）
2. 遇到”没有好解法”的问题怎么办？（贪婪、动态规划、近似算法）

下面一章一章来。

第 1 章 · 二分查找：猜数字的游戏

从一个游戏说起

我心里想一个 1～100 的数字，你来猜，每次我告诉你”大了 / 小了 / 对了”。

• 傻找：从 1 开始挨个猜。1、2、3……如果答案是 99，你要猜 99 次。
• 聪明的猜法：从 50 开始。我说”小了”——你一下子排除了 50 个数！再猜 75，再排除一半……每次都砍掉剩余的一半。

100 个数，最多 7 次必中。这不是运气，是可以证明的：每次排除一半，100 → 50 → 25 → 12 → 6 → 3 → 1，七步到底。

代码（Python 3）

def binary_search(lst, item):
    low, high = 0, len(lst) - 1      # 跟踪查找范围的"低"和"高"
    while low <= high:               # 范围没缩小到只剩一个元素
        mid = (low + high) // 2      # 中间位置（向下取整）
        guess = lst[mid]
        if guess == item:
            return mid               # 猜中了，返回位置（索引）
        if guess > item:
            high = mid - 1           # 猜大了 → 往左半边
        else:
            low = mid + 1            # 猜小了 → 往右半边
    return None                      # 没找到

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 7))    # 3（7 在索引 3 处）
print(binary_search(my_list, -1))   # None（没找到）

三个要点：① 列表必须有序（电话簿按字母排序才能折半翻）；② 位置从 0 开始编号，这个位置叫索引；③ Python 里 // 是整除，自动把中间位置向下取整。

大 O 表示法：别用秒，用”增速”

怎么比较”傻找”和”二分查找”谁好？用秒数是不行的——换台快一点的电脑结论就变了。大 O 表示法描述的是：当元素越来越多时，操作数的增长速度。

书里有个绝妙的例子：画 16 个格子。

• 算法一：一个一个画 → 16 次操作 → O(n)
• 算法二：把纸对折 4 次，一展开就是 16 个格子 → 4 次操作 → O(log n)（每折一次格子翻倍）

常见的大 O 阶梯，从快到慢：

体会一下差距：n = 16 时，O(log n) 要 4 次操作、O(n²) 要 256 次；n = 1024 时，前者 10 次，后者超过 100 万次。

书里最有冲击力的故事：Bob 给 NASA 火箭写着陆查找算法。10 亿个元素，线性查找要 10 亿毫秒 ≈ 11 天，二分查找只要 32 毫秒。他以为二分只快 15 倍——实际差 3300 万倍。这就是”增速”的意义。

最后记住：大 O 说的是最糟情况。查第一个就找到了固然好，但算法的性能保证按最糟情况算。

第 2 章 · 数组和链表：内存里的两种摆法

直觉

计算机内存像一排有地址的抽屉。要存一串待办事项，两种摆法：

• 数组：所有元素在内存里紧挨着。像电影院连座——再来一个朋友，中间没位子了，全家得搬家。
• 链表：元素各放各的，每个元素揣着下一个元素的地址的小纸条。像寻宝游戏：到第一个地址，纸条写着”下一个去 123”，到了 123 又写着”下一个去 847”……

运行时间对比（这是全章的核心）

结论：随机读取多 → 数组；频繁插入/删除 → 链表。“预留座位”（给数组预留空间）能缓解插入问题，但浪费内存且超了还得搬，不是完美方案。

补充 · 选择排序：本章的另一半（书里的主角）

原书第 2 章的标题就是”选择排序”——它是第 4 章快速排序的基石（原话：先熟悉它，理解快速排序会容易得多）。

场景：一份乐队列表，记录每支乐队的作品播放次数，要按播放次数从多到少排序。

思路：遍历列表，找出播放次数最多的乐队，放进新列表；再找第二多的；如此往复，直到有序。

为什么是 O(n²)：找一个最大值要 O(n)，要找 n 次，总时间 O(n × n)。有个疑问值得记：随着排序进行，需要检查的元素数在减少（n, n-1, …, 1），为什么还是 O(n²)？因为平均每次检查 n/2 个元素，总时间 O(n × ½ × n)——大 O 省略 ½ 这样的常量，所以写作 O(n²)。

代码（Python 3，原书为 2.7）：

def find_smallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))   # 弹出最小元素，追加到新列表
    return new_arr

print(selection_sort([5, 3, 6, 2, 10]))     # [2, 3, 5, 6, 10]

第 3 章 · 递归：自己调用自己的函数

一个例子：阁楼里找钥匙

祖母的阁楼里有个手提箱，箱子里套着盒子，盒子里还有盒子……钥匙在某一层。两种找法：

# 方法一：while 循环 + 一个"盒子堆"
def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile:                      # 盒子堆不空
        box = pile.grab_a_box()      # 取一个盒子
        for item in box:
            if item.is_a_box():
                pile.append(item)    # 是盒子 → 加进堆里待查
            elif item.is_a_key():
                print("found the key!")

# 方法二：递归——函数调用自己
def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)       # ← 递归！
        elif item.is_a_key():
            print("found the key!")

书里引 Stack Overflow 的那句话值得背下来：循环性能可能更高，递归可能更好理解，看你要什么。

基线条件 + 递归条件：缺一个就是无限循环

def countdown(i):
    print(i)
    if i <= 0:          # 基线条件：停！
        return
    else:
        countdown(i-1)  # 递归条件：调用自己

没有基线条件的 countdown 会 3、2、1、0、-1、-2……没完没了（Ctrl+C 都按不赢）。

调用栈：递归的”盒子堆”存在哪里？

每调用一个函数，计算机就往调用栈压入一帧（函数名 + 变量）。以 fact(3)（3! = 3×2×1）为例：

1. 调用 fact(3) → 压入 [FACT x=3]
2. 执行 3 * fact(2) → 压入 [FACT x=2]
3. 执行 2 * fact(1) → 压入 [FACT x=1] ← 栈顶
4. x == 1 命中基线条件 → 返回 1，逐层弹出：1×2=2 → 2×3=6

每个函数调用都有自己的变量（三个 FACT 帧里各有一个 x）。代价：栈很深 = 内存占用大。两种出路：改写循环，或尾递归（部分语言支持）。

第 4 章 · 分而治之与快速排序

分而治之 D&C：一种解决问题的”套路”

D&C 不是具体算法，是思路：① 找出最简单的基线条件；② 不断缩小规模，直到符合基线条件。

书里的例子：一块 1680×640 米的地，切成最大的正方形方块。每次从长边切出最大的方块（640×640 切两块），余下 640×400 的地——用同样的算法继续。切到基线条件（160 是 80 的整数倍，刚好切完）为止，答案：80×80。这就是欧几里得算法。

快速排序：最优雅的排序

def quicksort(arr):
    if len(arr) < 2:                 # 基线条件：空数组或单元素 = 有序
        return arr
    pivot = arr[0]                   # 基准值
    less    = [i for i in arr[1:] if i <= pivot]   # 小于基准值的子数组
    greater = [i for i in arr[1:] if i >  pivot]   # 大于基准值的子数组
    return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))     # [2, 3, 5, 10]

三步：选基准值 → 分区（partitioning：比基准值小的放左边、大的放右边）→ 对两个子数组递归快排 → 合并。

平均 O(n log n)，最糟 O(n²)：差在哪？

• 最糟情况：每次都拿第一个元素当基准值，而数组恰好有序 → 每次分区一边全空，调用栈高达 O(n)，总时间 O(n²)。
• 平均情况：随机选基准值 → 每层都平均分，栈高 O(log n) × 每层 O(n) = O(n log n)。
• 书里给的关键结论：最佳情况就是平均情况。快排比合并排序快的原因是常量更小——大 O 相同时，常量决定胜负。

补充 · 归纳证明与”平均情况就是最佳情况”

归纳证明：证明算法对所有输入都有效的两步法。书里的类比是爬梯子：

• 基线条件：我已经站在第一级横档上；
• 归纳条件：如果我站在第 n 级，就能爬到第 n+1 级。

两步合起来 → 我能爬到梯子最顶端。对快速排序：基线条件证明它对空/单元素数组管用；归纳条件证明”若对 n 个元素管用，则对 n+1 个也管用”——于是快排对任何长度的数组都管用。归纳证明与 D&C 是天生一对。

平均情况就是最佳情况：只要每次随机选基准值，快速排序的平均运行时间就是 O(n log n)。最糟 O(n²) 只在每次都恰好选到最大/最小元素时出现——随机选择时这种情形的概率极低，所以实际中快排碰上的几乎总是平均情况。

常量什么时候事关重大：书里的例子——两个打印函数，一个直接打印，一个打印前 sleep(1) 秒，两者都是 O(n)，但后者慢得多（c×n 里的 c 不同：10 毫秒×n vs 1 秒×n）。二分查找 vs 简单查找时常量无所谓（10 毫秒×n vs 1 秒×log n，n 一大二分仍碾压）；但快排 vs 合并排序（都是 O(n log n)）时，快排常量更小 → 实际更快。大 O 不同时常量靠边站，大 O 相同时常量定胜负。

第 5 章 · 散列表：让收银员 Maggie 替你记价格

直觉：从 O(n) 到 O(log n) 再到 O(1)

杂货店查价格：本子无序，翻每一行 O(n)；本子有序，二分查找 O(log n)；但顾客在排队等，都很痛苦。最好的办法是雇一个把所有价格背下来的 Maggie——报出任何商品价格都是 O(1)。

散列表就是机器版的 Maggie：散列函数把输入（键）映射成数组索引，值就存在那里。查询时同样先算索引，直接取——不用查找。

代码（Python 的 dict 就是散列表）

# 用途一：模拟映射（电话簿）
phone_book = {}
phone_book["jenny"] = 8675309
print(phone_book["jenny"])           # 8675309

# 用途二：防止重复（投票站）
voted = {}
def check_voter(name):
    if voted.get(name):
        print("kick them out!")      # 投过了，拦下
    else:
        voted[name] = True
        print("let them vote!")      # 让投，并记录

check_voter("tom"); check_voter("tom")
# let them vote! / kick them out!

DNS 解析（网址 → IP）、缓存（把生成的页面存起来）本质都是散列表。Facebook 缓存主页、About 页、条款页——把 URL 映射到页面数据。

两个性能关键

1. 冲突：两个键被映射到同一个位置 → 在该位置挂一个链表。链表太长说明散列函数太差（比如”按首字母分配”会让所有 A 开头的商品挤在 0 号位）。
2. 填装因子 = 已占位置 / 总位置。超过 0.7 就扩容一倍并重新散列。虽然扩容很贵，但摊平到每次操作，依然是 O(1)。

第 6 章 · 广度优先搜索 BFS：在关系网里找芒果销售商

图：节点 + 边

图模拟”一组连接”。用散列表就能表示：

graph = {}
graph["you"]   = ["alice", "bob", "claire"]   # 你的邻居
graph["bob"]   = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []; graph["peggy"] = []
graph["thom"] = []; graph["jonny"] = []       # 没有邻居 = 空列表

BFS 能回答两类问题：① 有没有路径？② 哪条最短？——按”几度关系”由近及远搜：先查你的一度朋友，没有销售商再查二度朋友。这保证第一个找到的就是关系最近的。

为什么必须用队列？

一度关系必须排在二度关系前面检查。队列（FIFO，先进先出）正好：先加入的先出队。用栈（LIFO）就乱了。

代码

from collections import deque

def search(name):
    search_queue = deque()          # 创建队列
    search_queue += graph[name]     # 邻居全部入队
    searched = []                   # 记录查过的人，防止死循环
    while search_queue:
        person = search_queue.popleft()      # 出队：先来的先查
        if person not in searched:
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            search_queue += graph[person]    # 不是 → 朋友排到队尾
            searched.append(person)          # 标记为查过
    return False

def person_is_seller(name):
    return name[-1] == "m"          # 书里的玩笑：名字以 m 结尾就是销售商

两个易错点：① 查过的人必须标记，否则”你↔Peggy 互为朋友”会无限循环；② 无向图的每条边其实都是环。运行时间 O(V + E)（顶点数 + 边数）。

第 7 章 · 狄克斯特拉算法：加权图的最短路径

BFS 找的是”段数最少”的路径，但每段代价不同时要算总权重。比如从乐谱换钢琴：每条边标着额外要贴多少钱，找总花费最少的换法。

四步

1. 找出最便宜的节点（当前开销最小）
2. 更新该节点邻居的开销（经它中转是否更便宜）
3. 重复，直到所有节点处理完
4. 沿父节点回溯，得到最终路径

graph = {}
graph["start"] = {"a": 6, "b": 2}        # 起点 → A 要 6，→ B 要 2
graph["a"] = {"fin": 1}
graph["b"] = {"a": 3, "fin": 5}          # B → A 只要 3！
graph["fin"] = {}

infinity = float("inf")
costs   = {"a": 6, "b": 2, "fin": infinity}       # 每个节点的开销
parents = {"a": "start", "b": "start", "fin": None}  # 父节点表
processed = []

def find_lowest_cost_node(costs):
    lowest_cost, node = float("inf"), None
    for n in costs:
        if costs[n] < lowest_cost and n not in processed:
            lowest_cost, node = costs[n], n
    return node

node = find_lowest_cost_node(costs)
while node is not None:
    cost, neighbors = costs[node], graph[node]
    for n in neighbors:
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:      # 经当前节点更便宜 → 更新
            costs[n] = new_cost
            parents[n] = node        # 父节点改为当前节点
    processed.append(node)
    node = find_lowest_cost_node(costs)

走一遍：直接到 A 要 6；但经 B 到 A 只要 2+3=5——更新 A 的开销为 5、父节点改为 B。经 A 到终点 5+1=6，比经 B 的 7 更短。最终路径：起点 → B → A → 终点，总开销 6。

⚠️ 大坑：有负权边就不能用。书里加了一条”用黑胶唱片换海报还倒找 7 美元”的负边，算法立刻选错路（35 美元 vs 实际最优 33 美元）。有负权边用贝尔曼-福德算法。

第 8 章 · 贪婪算法：完美是优秀的敌人

贪婪 = 每步选局部最优，企求全局最优。

• 教室调度（每间教室排最多的课）：每次选最早结束的课。这题贪婪恰好就是全局最优解！
• 背包问题（35 磅背包装最贵的）：每次拿最贵的——拿了 30 磅的音响（3000 美元）就装不下别的了；而笔记本+吉他 = 3500 美元。贪婪不是最优，但接近。小偷并不强求最优，够好就行。
• 集合覆盖问题（最少的广播台覆盖 50 州）：精确解要枚举 2ⁿ 个子集——5 个广播台 3.2 秒，10 个就要 1024 年。贪婪近似 O(n²)：每次选覆盖最多未覆盖州的台。

怎么识别 NP 完全问题（蛛丝马迹）

• 元素少时很快，元素一多就爆炸
• 涉及”所有组合 / 序列 / 集合”的问题
• 必须考虑所有可能情况、无法拆成小问题
• 能转换成旅行商问题或集合覆盖问题的——那它肯定是

认出来之后，别浪费时间找精确解，用近似算法。

第 9 章 · 动态规划：先解决小问题

背包问题逐步填格

小偷背包 4 磅，商品三件：吉他（1 磅 / 1500 美元）、音响（3 磅 / 3000 美元）、笔记本电脑（3 磅 / 2000 美元）。动态规划的做法是画一张网格：行 = 可选商品，列 = 1～4 磅的子背包，从上到下、从左到右填：

每格的公式只有一个：

cell[i][j] = max( 上一行的值，　本行商品的价值 + 剩余容量能装的最大价值 )

最后那格的 3500 是这么来的：装笔记本（2000）后剩 1 磅容量，查上一行”1 磅能装的最大价值”= 1500（吉他），2000 + 1500 = 3500 > 3000（单装音响）。这就是”先解决子问题”的意义：余下容量怎么装，答案早就算好了。

适用前提与坑

• 子问题必须离散、互不依赖——“去伦敦玩 2 天，想去巴黎（路上要半天）“的问题建不了模，因为子问题互相影响
• 行的排列顺序无关紧要；沿列往下走最大价值只增不减；最优解可能装不满（3.5 磅的钻石装进去，剩 0.5 磅什么也装不下）
• 同一套思路还能算最长公共子串 / 子序列（hish vs fish → ish）：DNA 相似性、git diff、编辑距离都是它

伪代码（两个字母相同/不同的公式）

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1        # 子序列：再加左/上的较大值
else:
    cell[i][j] = 0                          # 子序列：取 max(上, 左)

第 10 章 · K 最近邻 KNN：看邻居做判断

分类与回归

• 橙子还是柚子？ 柚子通常更大更红。看离它最近的 3 个邻居，橙子多就是橙子——这就是 KNN 分类。
• 回归是预测数值：预测 Priyanka 给电影打几分，找出最像她的 5 个用户，取平均分。

三个关键

1. 特征抽取：把物品变成可比较的数字（橙子用”个头+颜色”两个特征；用户用对各类电影的评分）。距离公式就是毕达哥拉斯：√((x₁-x₂)² + (y₁-y₂)²)，5 个特征也一样算。
2. 挑选特征决定成败：让用户给小猫图片打分来推荐电影？白搭——特征和品味无关。
3. 余弦相似度：两个品味相同的用户，一个打分保守（好片给 4 星）一个大方（好片给 5 星），距离公式会判他们不是邻居，余弦相似度比较角度就合理了。

经验规则：N 个用户取 √N 个邻居。应用：推荐系统、OCR（提取线段/点/曲线特征）、垃圾邮件过滤（朴素贝叶斯）。预测股市？书里明说：未来涉及的变数太多，不可能。

第 11 章 · 接下来学什么（每个一句话）

• 树：二叉查找树（左小右大，插入/删除 O(log n)，比有序数组更适合频繁变动的数据）；进阶：B 树、红黑树、堆、伸展树
• 反向索引：单词 → 包含它的页面。搜索引擎的核心
• 傅里叶变换：把歌曲拆成频率——MP3 压缩、Shazam 听歌识曲的原理
• 并行算法：多核也不等于翻倍快（管理开销 + 负载均衡）
• MapReduce：map（分发到几百台机器）+ reduce（归并），Hadoop 的核心
• 布隆过滤器：可能错报、绝不漏报的概率型结构；HyperLogLog：近似计数，省内存
• SHA：比较文件（散列值相同=同一文件）、存密码（单向，泄露也推不回原文）；用 SHA-2/3 或 bcrypt
• Diffie-Hellman：双方不用见面就能协商出加密密钥，破解难如登天
• 线性规划：在约束下最大化指标，图算法都是它的子集

写在最后：怎么用好这本书

1. 代码一定动手敲。书里反复强调：能原封不动地输入示例代码，你记住的内容会多得多
2. 每章的练习都做——通常一两分钟，是检验思路的路标
3. 原书代码是 Python 2.7 老写法（print x），练习时用 Python 3 重写正好当练手；配套代码在 egonschiele/grokking_algorithms
4. 读完的下一步：按第 11 章的地图，挑感兴趣的主题一头扎进去

书里自报的四类读者：业余程序员、培训班学员、需要重温算法的科班生、转行的数学/物理毕业生。如果你正打算啃《算法导论》——先把这本 200 页的小书读完，再去看大部头就不慌了。