Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People（算法图解）

引用

Bhargava, A. Y. (2024). Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People (2nd ed.). Manning Publications.

章节概要

第2版共320页、十三章，有Daniel Zingaro撰写的推荐序、作者序言，以及一节"关于本书"，说明如何使用本书、谁应该读和全书的组织结构。据出版社介绍，书中有400多幅插图，每章都有练习和代码示例，代码已更新为Python 3，新增了关于树（二叉搜索树、平衡树、B树）和NP完全问题的内容，以及关于数据结构在现代CPU上性能的讨论。每章开头列出读者将学到的内容，章末有小结（Recap）。

第1章：算法简介

全书的基础：以二分查找作为第一个算法，运行时间与大O表示法，运行时间的不同增长速度，大O作为最坏情况的度量，并初步介绍旅行商问题，作为运行时间极慢的一个例子。

第2章：选择排序

从内存的工作原理讲起，比较数组和链表在读取、在中间插入和删除方面的表现，然后介绍选择排序。本章说明它以第1章的大O表示法和对数为前提。

第3章：递归

讲基线条件和递归条件、栈与调用栈，以及递归时调用栈的行为。作者建议读者亲自运行代码，并至少用纸笔逐步跟踪一个递归函数；本章还引入了伪代码。

第4章：快速排序

把分而治之作为一种通用的解题策略，然后以快速排序作为它的第一个主要例子，再谈大O表示法，比较归并排序与快速排序，并对照平均情况与最坏情况。

第5章：散列表

讲散列函数和散列表的常见用途（查找、防止重复、用作缓存），然后讲决定性能的内部机制：冲突、性能和装填因子。

第6章：广度优先搜索

把图作为对网络建模的方式加以介绍，用广度优先搜索寻找步数最少的最短路径，讲队列、有向图与无向图以及拓扑排序。

第7–8章：树；平衡树

这是本版新增的内容。第7章借助文件目录定义有根树和二叉树，引入深度优先搜索并与广度优先搜索对比，还介绍了基于树的压缩算法——哈夫曼编码。第8章介绍二叉搜索树及平衡的重要性、AVL树与旋转、伸展树，以及B树及其优点。

第9章：狄克斯特拉算法

讲边带有行程时间时的加权图和最短路径，通过"换钢琴"的例子展开，并讨论狄克斯特拉算法失效的负权边以及算法的实现。

第10章：贪婪算法

讲贪婪策略（教室调度问题）、背包问题和集合覆盖问题、近似算法，以及如何识别没有已知快速精确解的NP困难问题。

第11章：动态规划

重新讨论背包问题，展示动态规划如何在网格中由子问题逐步构造出解，列出关于网格如何变化的一组问题，并通过实例说明如何为新问题设计动态规划解法。

第12章：K最近邻算法

机器学习的初步：用K最近邻进行分类、构建推荐系统、特征提取、回归，以及这种方法的用途和局限。

第13章：接下来如何做

简要介绍本书没有涉及的十种算法，包括线性回归、倒排索引、傅里叶变换、并行算法和MapReduce，并给出进一步阅读的建议。

核心概念

第1–4章：运行时间、排序与递归

• 大O表示法：算法运行时间如何随输入规模增长，按最坏情况给出。
• 二分查找：反复把有序列表折半，复杂度为O(log n)而不是O(n)。
• 数组与链表：读取快与插入、删除快之间的对比，与内存的工作原理相关。
• 递归与调用栈：基线条件、递归条件以及待完成调用组成的栈。
• 分而治之：把问题化为更小的实例，如快速排序。

第5–9章：散列表、图与树

• 散列表：平均为常数时间的查找，冲突和装填因子决定其性能。
• 广度优先搜索：用队列求无权图中的最短路径。
• 深度优先搜索与哈夫曼编码：树的遍历以及基于树的压缩算法。
• 平衡树：AVL树、伸展树和B树，在数据变化时仍能保持快速查找。
• 狄克斯特拉算法：边权非负的图中的最短路径。

第10–13章：难题及更远处

• 贪婪算法与近似：通过局部最优选择，快速得到NP困难问题的较好答案。
• 动态规划：先解子问题，再逐步构建整个问题的解。
• K最近邻：根据特征相似度进行分类和回归。

评析

优点

• 以图示和实例为中心。 出版社称书中有400多幅插图，公开的各章开头展示了这种风格：每个概念都先从一个具体场景出发（递归是阁楼里上了锁的手提箱，散列表是杂货店，广度优先搜索是穿越旧金山的公交路线），然后才给出算法。
• 篇幅短而覆盖广。 320页就从二分查找讲到NP困难问题、近似算法、动态规划和K最近邻，最后一章还指向更多主题。
• 第2版有所更新。 关于树和平衡树的新章节填补了第1版的空白，代码使用Python 3，源代码发布在GitHub上。
• 鼓励主动阅读。 例如递归一章要求读者运行代码并手工跟踪递归函数，出版社也说明每章都有练习。

局限

• 重直观而非证明。 出版社"不需要高深数学"的定位意味着正确性和运行时间是通过例子来解释，而不是推导出来的；修读大学课程的学生仍需要一本有证明的教材。
• 每个主题都讲得简短。 在插图很多的320页中容纳十三章，每种算法的篇幅有限；第13章明确只是概览十个主题。
• 只用Python。 全部代码都是Python，使用其他语言的读者需要自己改写。

在课程中的定位

本书是本课程中最直观的入门读物，与Wengrow的 A Common-Sense Guide to Data Structures and Algorithms 互为搭配。Wengrow在数步数和分析日常代码上花的篇幅更多，并为每道练习提供解答；Bhargava的分析较轻，但覆盖更多算法内容，包括平衡树、狄克斯特拉算法、NP困难问题和K最近邻。觉得其中一本讲解难懂的读者，可以换另一本看。

读完这两本之后，Goodrich、Tamassia和Goldwasser的 Data Structures and Algorithms in Java 以及Pat Morin免费提供的 Open Data Structures 会给出带有实现和证明的完整大学课程内容。Peter Brass的 Advanced Data Structures 和Chris Okasaki的 Purely Functional Data Structures 是很久以后才读的专门著作。贪婪算法和动态规划两章也可以作为算法课程的轻松预习。

如何使用本书

本书适合会一点编程（任何语言均可）、想直观入门算法的读者：自学的程序员、在第一门数据结构课程之前或期间的学生，以及准备技术面试的人。有Python经验会有帮助，但示例都很短。

实用阅读计划：

• 核心： 按顺序读第1–6章。每章都建立在前一章之上：大O、数组与链表、递归、分而治之、散列表，然后是图。
• 树与图： 第7–9章。第8章的平衡树初读时可以略读，但第9章完成了第6章开始的最短路径话题。
• 解题策略： 第10–11章最好一起读，因为第11章重新讨论了第10章的背包问题。
• 选读： 对机器学习感兴趣的读者读第12章；第13章可作为阅读清单。

运行GitHub仓库中的Python代码并改变输入，像书中建议的那样手工跟踪递归函数和图搜索。进入下一章之前先完成本章练习。如果是为课程而读，可在每个部分之后阅读一本正式教材的相应章节，补上本书省略的证明和分析。