《算法导论》第三版勘误与建议

本文主要是介绍《算法导论》第三版勘误与建议，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近在读由殷建平、徐云、王刚、刘晓光、苏明、邹恒明和王志宏七位老师翻译，机械工业出版社出版的《算法导论（第3版）》这本书，发现了一些不太恰当的地方，在这里进行一下记录，以方便日后再读时查阅。此处按照页码顺序进行排序，由于我现在尚远远没有读完此书，故只能找出已读部分的一些进行整理，日后会不断完善。如有改得不太恰当之处，还请诸位大神不吝留言赐教。

第一部分基础知识

第4章分治策略

1、第45页底部，“我们用常数次矩阵乘法的代价减少了一次矩阵乘法”，应该改为“我们用常数次矩阵加法的代价减少了一次矩阵乘法”。

2、第56页，式（4.21）容易引起歧义，改为下式更为恰当：

$T(n)=\Theta (n^{log_{b}a})+\sum_{j=0}^{(log_{b}n)-1}a^{j}f(n/b^{j})$

第57页和58页的相关公式与之相同。

第二部分排序和顺序统计量

第6章堆排序

1、第88页第二行，“高度为h的堆最多包含⌈ $n/2^{h+1}$ ⌉个结点”应该为“含有n个元素的堆中，至多包含⌈ $n/2^{h+1}$ ⌉个高度为h的结点”。

第三部分数据结构

第10章基本数据结构

1、第135页，“对象的分配与释放”小节中的“自由的”、“自由表”，改为“空闲的”和“空闲表”似乎更为恰当一些。

2、第156页，“完全散列”原文为“perfect hash”，译为“完美散列”似乎更为合适，也更能表达其具有优异的性能的意思。

第12章二叉搜索树

1、第169页，倒数第11行“表示这个关键字在n个关键字集合中的秩（rank）”，这里的“秩”改为“排名”或者“名次”似乎更为合适。

第七部分算法问题选编

第34章 NP完全性

1、第628页，NP完全语言的定义中的第2条“对每一个 $L^{'}$ ∈ $NP_{2}$ ”中的“ $NP_{2}$ ”应为“NP”。

2、第634页倒数第8行，“则检查每一种赋值需要 $\Omega (2^{n})$ 时间”，容易引起歧义，应该为“把每一种赋值都检查一遍需要 $\Omega (2^{n})$ 时间”或“检查所有的赋值需要 $\Omega (2^{n})$ 时间”。

3、第637页右上部中的真值表中的括号多写了一个右括号，正确写法可见真值表的题注。

4、第639页，图34-14下面第一段，“该公式的一组可满足赋值为 $x_{2}=0,x_{3}=1,x_{1}$ 为0或者1”应该改为“该公式的一组可满足赋值为 $x_{2}=0,x_{3}=1,x_{1}$ 为0或者1”，并且该小段原本是图34-14的说明中的一部分，而不是一段正文。

5、第642页，第二行，“在后一种情况中，回路必须重新进入附件图以访问顶点[u,v,1]到[u,v,6]。类似地，如果回路是从顶点[u,v,1]进入的，则必须从顶点[u,v,6]退出”，应该改为“在后一种情况中，回路必须重新进入附件图以访问顶点[v,u,1]到[v,u,6]。类似地，如果回路是从顶点[v,u,1]进入的，则必须从顶点[v,u,6]退出”。

6、第642页，图34-16的说明中的最后“是通过顶点[u,v,1]、[u,v,6]、[v,u,1]和[v,u,1]完成的”应该改为“是通过顶点[u,v,1]、[u,v,6]、[v,u,1]和[v,u,6]完成的”.

正如译者序中所说“由于水平有限且工作量巨大，译文中一定存在许多不足之处”，像是这么大部头的一本经典算法书籍，翻译的过程中出现些许错误是在所难免的。但是有些错误可能会对我们这些菜鸟学习者造成一些很难理解的问题。我在这里仅仅是列出了我在学习时发现的一些个人认为不太合理的地方，我的这些修改肯定也会存在一些不合理的地方，希望有大神发现能够给与之处，不吝感激。这本书我尚未完全读完，本篇文章也将会随着学习的进度不断修改。

这篇关于《算法导论》第三版勘误与建议的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！