算法设计手册

引用

Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.

章节概要

全书分两部分，共22章，后接参考文献和索引；正文页码排到约第718页，全书共793页。第一部分“实用算法设计”（第1–13章）讲授设计和分析算法的方法。第二部分“算法漫游指南”（第14–22章），出版社称之为供翻阅的目录，收录实践中经常出现的75个问题，并附有实现和文献的线索。Skiena 本人的网页把本书描述为重设计而非重分析。

第1–2章：算法设计导论；算法分析

开头两章分别介绍算法设计（第1章）和算法分析（第2章），后者约四十页。出版社把本书的风格描述为“不堆砌定理与证明”（no theorem-proof），即直观而非形式化的口吻，分析也是用这种口吻来讲的。

第3–4章：数据结构；排序

数据结构和排序在第一部分里各有专门的章节，所以本书并不是简单地假定读者已经掌握它们；不过，目录没有显示这两章对先修知识的预期有多高。

第5–6章：分治法；散列与随机算法

两章讲技巧。出版社列出本版在分治法、散列和随机算法方面的新增或扩充内容，与这些章节的主题相符。

第7–8章：图的遍历；加权图算法

两章合计约八十五页，从遍历讲到加权问题。图在第二部分里再次出现，分别在多项式时间问题和NP难问题两章中，因此正文页码中大约四分之一与图有关。

第9–10章：组合搜索；动态规划

第9章讲组合搜索；第10章讲动态规划，约四十七页，是第一部分最长的一章。

第11–13章：NP完全性；应对困难问题；如何设计算法

第一部分以一组关于难解性的章节收尾：先讲NP完全性意味着什么，再讲遇到这类困难问题时的对策。出版社把近似算法列为新增或扩充的内容之一，但没有说明由哪一章承载。这一部分的最后一章题为“如何设计算法”，只有六页。

第14章：算法问题目录

通向第二部分的两页入口；第二部分以“漫游指南”的形式从第435页开始。出版社称，这份目录会为每个问题把读者引向解决问题的正确道路。

第15–19章：数据结构；数值问题；组合问题；图问题（多项式时间）；图问题（NP难）

按问题种类组织的目录条目。第15章回到数据结构，只是现在放在目录之中；第18章和第19章把图问题分成多项式时间可解的和NP难的两类。

第20–22章：计算几何；集合与字符串问题；算法资源

目录以几何问题（目录各章中最长，约五十六页）、集合与字符串问题，以及很短的最后一章“算法资源”结束。出版社称本书提供指向 C、C++ 和 Java 实现的链接。

核心概念

第一部分：实用算法设计（第1–13章）

• 算法分析：判断设计的效率，被当作实用工具来对待。
• 分治、散列、随机化：各有专章的设计技巧。
• 图的遍历与加权图：图这部分的核心。
• 动态规划与组合搜索：处理优化问题和穷举类问题的方法。
• NP完全性：用来识别那些很可能没有高效精确算法的问题的术语。

第二部分：算法漫游指南（第14–22章）

• 问题目录：按问题类别组织条目，读者可以由问题而不是由算法入手查找。
• 问题类别：数据结构、数值、组合、图（多项式时间与NP难）、几何、集合与字符串，目录各章即按此划分。

评析

优点

• 围绕“识别问题”来组织。 目录部分让读者可以从问题的形态出发，这与多数算法教材逐个技巧推进的顺序不同。Skiena 的网站上还列有算法资源库（Algorithm Repository）和程序。
• 易于读懂。 出版社强调“不堆砌定理与证明”的风格、突出显示的“带走的教训”（take-home lessons），以及来自实际应用的“战争故事”（war stories）。
• 练习材料丰富。 习题中有求职面试题，新版增加了一百多道题，其中包括来自 LeetCode 和 HackerRank 的题目。作者的网站链接了题解维基、讲义和讲课视频。
• 正面应对困难问题。 NP完全性、应对困难问题的策略，以及单独一章NP难图问题，让学生看到在预期没有高效算法时该怎么办。

局限

• 有意把证明压到最少。 想认真跟踪正确性和运行时间证明的读者，需要配一本更形式化的教材。
• 代码用C语言。 出版社说，许多算法以C代码给出，所以使用其他语言的读者要自己翻译，或者借助实现链接。
• 一半是参考内容。 出版社称第二部分供翻阅和查考；从头读到尾，它只是一份目录，而不是一串循序渐进的课程。

在课程中的定位

在本课程之中，Skiena 的书介于较平易的入门书和严谨的教材之间。Cormen 的 Algorithms Unlocked 是数学要求不高的简短入门书，Roughgarden 的 Algorithms Illuminated 是带免费视频讲座的、口语化的四部分讲解；两者都可以先读。Cormen 等人的 Introduction to Algorithms 是以严谨讲解和伪代码著称的综合教材，需要证明时是自然的配套读物。

对于第11–12章和第19章的困难问题部分，专门的书可以走得更远：Vazirani 的 Approximation Algorithms 与 Williamson 和 Shmoys 的 The Design of Approximation Algorithms 对近似算法讲得深入得多，Mitzenmacher 和 Upfal 的 Probability and Computing 则是进入随机算法的高级途径。

如何使用本书

本书适合已经会编程、接触过基本数据结构的学生，也适合准备技术面试的从业者，后者是出版社提到的用途之一。想判断自己面对的是哪一类问题的人，也能从中受益。

一个实用的读法：

• 核心（第一部分）： 内容熟悉的话，第1–4章快速过一遍；第5–10章按顺序读，它们是主要的技巧库；第11–12章读难解性；第13章作为这一部分收尾的简短设计章节。
• 参考（第二部分）： 读完入口一章后，在遇到具体问题时查目录，顺着它给出的实现和进一步文献的线索走，而不是一章接一章地读。
• 练习： 做习题，包括面试风格的题目，并用作者网站上的题解维基和讲课视频核对。
• 搭配： 手边放一本像 Introduction to Algorithms 这样严谨的教材，用于查证明；再用自己的语言实现几个算法，与书中的C代码对照。