01 / 导读
导读
引用
Wengrow, J. (2020). A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills (2nd ed.). The Pragmatic Bookshelf.
章节概要
第2版共506页、二十章，每章以"Wrapping Up"（小结）和一组练习结束，书末附录给出所有章节练习的解答。序言介绍本书的读者对象、本版新增内容、阅读方法、代码示例和在线资源；出版社提供源代码下载。代码示例使用JavaScript、Python和Ruby。据出版社介绍，第2版为每一章都加了练习，并新增了关于递归、动态规划、在日常代码中使用大O记号以及堆和字典树的章节。
第1–3章：为什么数据结构很重要；为什么算法很重要；O Yes! 大O记号
本书的方法在第1章中确立（该章有免费节选）：一个操作的速度不是用时间来衡量，而是用它所需的步数来衡量。这一章计算数组读取、查找、插入和删除各需多少步，然后把数组与集合比较——在集合中，"不允许重复"这一条规则就改变了插入的代价。第2章介绍有序数组，比较二分查找与线性查找；第3章把数步数的方法提炼为大O记号，包括对数和O(log N)。
第4–6章：用大O加快代码；借助与不借助大O的代码优化；针对乐观情形的优化
这三章借助简单排序算法深化分析。冒泡排序（有免费节选）展示了一个平方级算法，以及如何用线性解法取代平方级解法；选择排序说明为什么大O忽略常数，但同一类别中的两个算法仍可能有差别；插入排序引入最好、最坏和平均情况。
第7章：日常代码中的大O
这是新增的一章，也有节选，把分析应用于简短的实用函数：偶数的平均值、拼词、数组抽样、服装标签、回文检查、获取全部商品以及密码破解等。开头说明，确定当前代码的大O是优化的第一步。
第8–9章：用哈希表实现极速查找；用栈和队列写出优雅的代码
哈希表通过哈希函数、冲突以及高效哈希表的条件来讲解，并展示了它在组织数据和加快代码两方面的用途。栈和队列被作为受约束的数据结构和抽象数据类型来介绍。
第10–13章：用递归递归地递归；学会用递归来写；动态规划；追求速度的递归算法
递归部分从如何阅读递归代码和基准情形讲起，经过递归问题的类别与自顶向下的思维方式（爬楼梯问题、生成变位词），再到通过记忆化和自底向上两种方式实现的动态规划。第13章把递归用于划分、快速排序及其最坏情况、快速选择，并指出排序可以成为解决其他问题的关键。
第14–17章：基于节点的数据结构；用二叉搜索树加速一切；用堆分清轻重缓急；试试字典树
讲链表和双向链表（包括用它们实现的队列），带插入、删除和遍历的二叉搜索树，作为优先队列的堆（包括用数组存储堆以及"最后一个节点"问题），以及用于实现自动补全的字典树（trie）。
第18章：用图连接一切
讲有向图、面向对象的实现、深度优先搜索和广度优先搜索及其效率、加权图和迪杰斯特拉算法。
第19–20章：应对空间限制；代码优化技巧
第19章把大O推广到内存，讨论时间与空间的权衡以及递归隐藏的空间开销。第20章汇总了实用的优化策略：从当前的大O出发，设想可能达到的最佳大O，寻找"神奇查找"（magical lookups），识别模式，使用贪心算法，以及更换数据结构。
核心概念
第1–7章：衡量效率
- 步数而非秒数：操作的速度就是它所需的步数，与硬件无关。
- 大O记号：在忽略常数的前提下，描述步数如何随N个数据元素增长。
- 最好、最坏与平均情况：同一算法在不同输入下表现不同的原因。
- 二分查找：每一步把有序数组折半，这就是O(log N)的来源。
第8–13章：查找、约束与递归
- 哈希表：借助哈希函数按键查找，并通过处理冲突保持查找速度。
- 抽象数据类型：由所允许的操作来定义的栈和队列。
- 递归与基准情形：用问题自身更小的实例来求解问题。
- 记忆化与自底向上的动态规划：消除对重叠子问题的重复递归调用。
第14–18章：基于节点的结构
- 链表：由链接相连的节点，读取和插入的代价与数组不同。
- 二叉搜索树与堆：为快速查找而有序的树，或为快速取得最高优先级元素而有序的树。
- 图搜索与迪杰斯特拉算法：深度优先和广度优先遍历，以及加权图中的最短路径。
第19–20章：空间与优化
- 空间复杂度：应用于内存的大O，包括递归使用的调用栈。
- 优化技巧：寻找更快算法的有意识的策略。
评析
优点
- 单一而具体的效率观念。 免费的第1章展示了这种方法：在任何记号出现之前，所有关于速度的说法都归结为在小例子上数步数，因此读者是从经验而不是从定义出发建立大O的概念。
- 分析普通代码。 第7章分析真实代码库中常见的简短函数，第20章把分析转化为一套优化习惯，从而把理论与在职程序员实际编写的代码联系起来。
- 练习附完整解答。 每章都以练习结束，附录给出全部二十章的解答，便于自学。
- 多语言示例。 JavaScript、Python和Ruby的示例让在职的Web开发者容易上手；出版社没有列出编程以外的先修要求。
局限
- 分析不够形式化。 大O是通过数步数引入的；目录中看不到形式化定义、正确性证明或递推式求解，准备学习理论课程的学生需要一本更严谨的教材。
- 内容有所取舍。 归并排序、平衡搜索树、最小生成树等标准算法没有出现在节标题中；本书涵盖了核心结构，但不覆盖大学课程的全部内容。
- 只有动态类型语言的示例。 代码使用JavaScript、Python和Ruby；课程使用Java或C++的学生需要自己改写实现。
在课程中的定位
在本课程中，本书与Bhargava的 Grokking Algorithms 同为平易的入门读物。两者都适合会编程但没有计算机科学背景的读者：Wengrow在数步数和分析日常代码上花的篇幅更多，并配有带解答的练习；Bhargava更多依靠插图，还涉及贪心算法和近似算法等主题。先读哪一本都可以；想对同样的核心思想获得第二种讲解的读者，两本都读也很合理。
读完本书后，课程转向完整的教科书。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 则是要到很久以后才读的专门著作。
如何使用本书
本书面向希望为日常工作理解数据结构与算法的程序员，包括自学和培训班出身的开发者，以及正在修读第一门数据结构课程的学生。读者只需掌握任意一种语言的基本编程和中学算术；对数在第3章中有讲解。
实用阅读计划：
- 核心（按顺序）： 第1–9章。本书的分析是逐步累积的，第7章对真实代码的分析值得认真完成。
- 递归部分： 把第10–13章作为一个整体来读；讲动态规划的第12章依赖于前两章。
- 数据结构： 第14–18章。时间不够时，初读可以跳过堆和字典树（第16–17章），但图（第18章）不应跳过。
- 综合： 第19–20章为全书收尾，适合在技术面试或课程考试前复习。
先做每章的练习再看解答；用自己最常用的语言把可下载的代码敲一遍并运行，对同一任务的慢版本和快版本计时，亲眼看看步数的差别。如果正在修读大学课程，可以在读完本书每个部分后再读一本正式教材的对应章节，当形式化的讲解难以理解时，再回到本书的解释。
