书评：《算法设计手册》
作者：Joseph Kong
《算法设计手册》
出版社： Springer；第 2 版（2008 年 7 月）
印刷版定价： $89.95
电子版定价： $69.99
ISBN-10： 1848000693
ISBN-13： 978-1848000698
页数： 730
这是过去一年里我读过的最好的书之一。它带你稳步游览算法世界，引导恰到好处（不过绝对不适合编程新手）。
《算法设计手册》分为两部分。第一部分为第 1–10 章，介绍算法设计基础，包括数据结构、动态规划、回溯、建模等内容。每章还包含若干“战记”，详述 Skiena 处理真实问题的经验。这些故事颇具趣味，能缓解部分晦涩内容的枯燥。
第二部分为第 11–19 章，是算法资源（例如数据结构、实现等）的目录，供浏览与查阅。其思路是：与其从零开始解决算法问题，不如把已有的方案作为起点（或直接用作答案）。
第 1 章 算法设计导引，先描述什么是算法，再深入讲解建模——把问题拆解为一个或多个已被充分理解的问题（这些问题的解答可在本书第二部分找到）。
第 2 章 算法分析，描述算法效率，引入“大 O”记号。Skiena 对“大 O”的讲解相当出色，明显优于许多其他教材。
第 3 章 数据结构，在算法设计的语境下介绍数组、链表、栈、队列、字典、二叉树、优先队列和哈希表。我认为这一章是非常好的复习材料。
第 4 章 排序与查找，强调排序如何用于解决其他问题。还讲述了二分查找和分治思想，并详尽介绍若干算法，包括堆排序、归并排序、快速排序和分布排序。
第 5 章 图的遍历，先介绍不同类型的图（有向图、无向图、带权图、无权图等）以及图所用的数据结构（即邻接矩阵和邻接表），再描述图遍历技术（即广度优先搜索和深度优先搜索）。
第 6 章 加权图算法，是第 5 章的延续，深入带权图，包括生成树的讨论。本章中关于用电话输入文本的战记颇为有趣且富有启发性——老式电话中输入 2 可能代表字母 A、B 或 C，以及如何通过上下文识别正确字母。
第 7 章 组合搜索与启发式方法，描述如何系统性地遍历问题（或搜索空间）的所有可能解（或配置）。这里讲述了回溯和搜索剪枝的概念。我尤其喜欢 Skiena 演示如何解任意数独问题的部分，它真正凸显了回溯和搜索剪枝的威力。
第 8 章 动态规划，如其名所示，介绍动态规划。Skiena 对该主题的讲解相当清晰易懂。
第 9 章 难解问题与近似算法，介绍证明某问题不存在高效算法的技术。其思路是：如果能证明寻找高效算法毫无意义，就可以把精力放到别处。
第 10 章 如何设计算法，只是一份四页的清单，设计算法时需要牢记。虽然算不上完整章节，但我非常感激这份列表。
第 11–19 章 是算法资源目录，详尽介绍数据结构、数值问题、组合问题、图问题、计算几何、集合与字符串问题。这部分有个亲切的昵称——“算法搭车客指南”。如果非要对此书挑点毛病，那就是部分内容偏枯燥晦涩——绝不是适合懒散周日下午闲读的书。但这些都是小瑕疵。
归根结底，《算法设计手册》是一本扎实的书，如果你还没读过，应该读一读。
Joseph Kong 是自学成才的计算机爱好者，涉足漏洞开发、逆向代码工程、rootkit 开发和系统编程（FreeBSD、Linux 和 Windows）等领域。他是广受好评的《Designing BSD Rootkits》和《FreeBSD 设备驱动程序开发》的作者。有关 Joseph Kong 的更多信息，请访问 <www.thestackframe.org> 或在 Twitter 上关注他 @JosephJKong。
最后更新于