“参照国外读者的评价,找到你需要的书。”在你决定购买本书之前,本栏目将努力向读者朋友们呈现公正客观的评价。

如果你发现这是本好书,请不要忘记收藏

5星评价:目前最好的算法教科书

有用:77/81

作者:Kevin P. Murphy (不列颠哥伦比亚大学计算机系教授)

Robert Sedgewick和Kevin Wayne的《算法》(第四版,由Addison-Wesley于2011年三月出版)是我读过的最棒的计算机科学方面的书籍之一。它应该是所有程序员以及计算机科学专业的学生的必读书籍——它的目标是覆盖“每个程序员都应该了解的50个算法”。下面我就来说说为什么我觉得这本书是如此的优秀。

《算法》包含了具体的源代码(基于一个Java的子集),这和它的主要对手——由Cormen、Leiserson、Rivest和Stein (CLRS)完成的《算法导论》(An introduction to algorithms)——非常不同。这一点非常重要,因为它意味着学生们可以使用这些代码去解决许多真实的问题。这些算法产生了从网络搜索到基因组学的许多有趣和令人激动的应用,这些应用也贯穿了全书。(这本书的网站上提供了所有的源代码和数据)

对真实代码的一种很自然的担心是它们可能会影响对概念的理解。但在这本书中,作者通过精心定义的抽象数据类型(队列、背包、哈希表、树、有向无环图等类)赏心悦目的创造了许多既有可读性又非常准确的实现。

使用真实代码的另一个好处是迫使你解决一些容易被忽略却十分重要实现细节。例如,大家都知道并归排序需要辅助性内存空间。在CLRS的伪代码中,作者在他们的并归函数内部分配的临时存储空间。但在实践中,仅分配一次临时存储空间并将它作为一个指针传递给并归函数(或是将它作为并归排序类的一个私有成员)将会高效的多。这种重要的技巧你又可以从哪里学到呢?

除了代码的展示之外,本书也用清晰的语言解释了这些方法。本书非常与众不同的一点就是包含许多详细的例子来说明这些算法在处理真实数据时的行为和表现。(除非你真的实现了这些算法,否则是很难得到这些数据的!)

这本书的另一个优点是它严格遵守了软件工程的最佳实践:先写API,再写单元测试或是实现一个使用该数据结构或算法的应用(用例),最后才考虑应该如何实现这个API。另外,本书在许多时候还讨论了同一API的多种实现,它们在简洁性、速度和内存使用上的折中都各有不同。

对于数据结构,使用“类”是很自然的,但对于算法作者也采用了这种描述方式,特别是图算法。这使得算法能够进行预处理并保存一些内部状态,然后再为使用者提供服务。这种方式比传统的无状态的函数式的算法更加通用。

这本书的每一节都有大量的练习,分为“简单”、“提高”和“实验”三种,它的网站提供了部分练习的解答。

这本书的一个特别之处是除了理论之外,它还含有许多经验性的算法题目。它展示了算法的不同实现对于不同规模问题的实际运行时间,并用这些数据作为传统理论分析的补充。

相比CLRS,这本书的一个小小的好处是没有那么厚(约1000页,而CLRS有1300页)。另外,这本书也有Kindle版本,这意味着你可以不用带着一本能够把你的背压断的大部头到处跑了。(尽管Kindle版本的排版并不尽如人意)

显然,《算法》和CLRS的内容有许多重叠。从书的目录来看这一点并不明显,因此我写了一份更加详细的列表来列出这本书讨论了的所有问题。

全书的组织非常好,前面介绍过的内容(和代码)会在后面得到多次应用(例如:堆->优先队列->最小生成树的Prim算法)。书中的话题也会越来越高级。因此读者最好一页一页的顺序的阅读本书。

下面是我制作的一份书中的话题总结,因为它们从目录上看起来并不明显。

第一章 基础

1.1. 基础编程模型

-- Java入门

-- API与各种库

-- 二分查找(递归)

1.2. 数据抽象

-- 面向对象基础

-- 避免“宽”接口

1.3. 背包、队列和堆栈

-- 泛型(C++中被称为模板)

-- 迭代器

-- 表达式求值的Dijkstra的双堆栈算法

-- 动态数组

-- 链表与指针

1.4. 算法分析

-- 经验性算法

-- 大O记法(“线性对数”的意思是O(NlogN))

-- 随机化的算法

-- 内存的使用

1.5. 实例分析:union-find算法

-- 应用:动态连通性(p、q是否是在同一个集合中?)

-- 三种实现,最后得到一种经典的算法

第二章 排序算法

2.1. 初级排序算法

-- 选择排序

-- 插入排序

-- 希尔排序

2.2. 并归排序

-- 自顶向下的并归排序(递归)

-- 运行时间是NlogN的证明

-- 自底向上的并归排序

-- 证明排序所需的比较次数的下界是NlogN

2.3. 快速排序

-- 实现

-- 分析

-- 使用三向切分加快对等键情况的排序

-- 证明排序成本的下界是N乘以键的分布的熵

2.4. 优先队列

-- 堆

-- 优先队列

-- 使用优先队列解决得到一列数中最大的N个数的问题

-- 使用索引优先队列实现N个有序列表的多向合并

-- 堆排序

-- 各种排序算法的比较(速度、稳定性、原地性、额外空间的使用)

-- 顺序统计以及在O(N)时间内找到中位数

第三章 查找

3.1. 符号表(也叫做关联性数组)

-- 符号表与有序符号表(键可以被比较,因此可以得到最大和最小键)

-- 在一份大文档中统计词频

-- 无序链表中的顺序查找

-- 有序数组中的二分查找

3.2. 二分查找树

-- 二分查找树的性质(父节点比左子节点大,比右子节点小)

-- get和put方法的实现,以及对其所需时间为O(logN)的分析

-- 查找最小元素、删除最小元素、删除任意元素

-- 中序遍历

3.3. 平衡查找树

-- 2-3树和红黑树

3.4. 哈希表

-- 哈希函数(例如,取模以及Horner法则)

-- 拉链法

-- 线性探测法

3.5. 应用

-- 去重

-- 字典查找

-- 逆向索引

-- 文件索引

-- 稀疏矩阵向量的乘法

第四章 图

4.1 无向图

-- 临接表的表示

-- 深度优先搜索

-- 广度优先搜索

-- 基于广度优先搜索的单点最短路径算法

-- 基于深度优先搜索的连通分量算法

-- 使用深度优先搜索判断G是否是无环的

-- 使用深度优先搜索判断G是否是二分的

-- Kevin Bacon游戏(六度理论)

4.3. 加权无向图的最小生成树

-- Prim算法

-- Kruskal算法

4.4. 加权图中的最短路径

-- Dijkstra算法

-- 加权有向无环图中的最短路径

-- 调度问题的关键路径算法

-- 加权有环有向图中的最短路径(Bellman-Ford算法与负权重边的检测)

-- 套汇

第五章 字符串

5.1. 字符串排序

-- 键索引计数法(基数排序)

-- 低位优先的字符串排序

-- 高位优先的字符串排序

-- 适用于带有重复前缀字符串的三向字符串快速排序

5.2. 字典查找树

-- R向字典查找树

-- longestPrefixOf方法(最长公共前缀)

-- 三向字典查找树(R向数组的二分查找树表示)

5.3. 子字符串查找

-- 暴力方法

-- KMP算法

-- Boyer-Moore算法

-- Rabin-Karp指纹算法

5.4. 正则表达式

-- 语法

-- 使用非确定性有限状态自动机判定字符串是否在特定的语言中

5.5. 数据压缩

-- 基础知识

-- 游程编码

-- 哈夫曼压缩算法

-- LZW压缩算法(基于字典查找树)

  1. 背景

6.1. 基于优先队列的事件驱动模拟

6.2. B树

6.3. 后缀数组

-- 找出最长重复子字符串

-- 字符串的索引(上下文中的关键字)

6.4. Ford-Fulkerson最大流量算法

-- 寻找最短增广路径

-- 最大二分图匹配问题向最大流量问题的归约

-- 最大流量问题和最短路径问题向线性规划问题的归约

6.5. NP完全性

五星评价:温故而知新

有用:6/6

作者:Edward A. Averil

在20年的内核编程、设备驱动、进程控制和其他实时系统的工作之后,我的算法知识绝大部分都已经荒废了。现在当我回头再次需要完成一些高层次的工作时,我就遇到麻烦了!

但这本书里有我需要的一切,而且它比伴随我成长的Knuth的那本书要易懂的多。我也非常喜欢书中的范例实现,当我看到代码时一些疑惑就自然消解了。

对于所有正在转换工作领域并需要重新掌握那些基本编程技巧的人来说,我强烈的推荐这本书!

四星评价:当年我要是能有这本书……

有用:0/0

作者:T. A. Lovern

我真希望当年我在上算法课时使用的是这本书。书中的例子都是精心选择的,概念诠释的很充分,代码简明厄要。全书的章节一步一步的构建起了一个算法库,这使得跳过部分章节直接阅读特定的例子变得有些困难。所有这些代码和库都可以从这本书的网站上获取。

所有代码都是用Java写的,这正合我意。

我向我的组员们推荐了这本书——并非必读,但它应该成为他们的工具箱中的一员。

在优化仓储操作时对最短路径算法的需求让我找到了这本书。我大概了解我所需要的算法,但还需要一些帮助。我只看了在线章节两分钟就决定要买这本书。这是个非常正确的决定。