Name: Introduction to Algorithms, Third Edition (International Edition)
Availability: InStock
Rating: 9.3 (24 reviews)
Author: T Cormen, C Leiserson, R Rivest, C Stein
ISBN: 9780262533058

再好的书变成教科书也会变得乏味，不过这应该是算法里面比较靠谱的书了。

读过一点，可惜没能坚持下去，大师的书还不是艰深晦涩

CS的书就不能薄那么一点点嘛。 @2012-12-20 21:46:35

动态规划算法的设计可以分为如下四个步骤：
1 描述最优解的结构。
2 递归定义最优解的值。
3 按自底向上的方式计算最优解的值。
4 由计算出的结果构造一个最优解。

在最好的情况下，k=0，因此s'=s+q，并且立刻能得出偏移s+1，s+2，s+3，…s+q-1。

In the best case, k=0,so that s‘=s+q, and we immediately rule out shifts s+1,s +2;...,s+q-1.

即π[q]是Pq的真后缀P的最长前缀长度。

π[q] is the length of the longest prefix of P that is a proper suffix of Pq.

考虑对数组A中的n个数进行排序：首先找出A中的最小元素，并将其与A[1]中的元素进行交换。接着找出A中的次小元素，并将其与A[2]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环不变式是什么？为什么它仅需要在头n-1个元素上运行，而不是在所有n个元素上运行？以Θ形式写出选择排序的最佳和最坏情况下的运行时间。

如果一个节点是红的，则它的两个儿子都是黑的。

如果一个节点是红的，那它的父亲一定是黑的

作为《算法导论》的作者之一，我肯定有偏爱。所以我只给出客观的理由，让其他人发表意见。

1· 尺寸。该书共有1312页（包括封面），涵盖了广泛的主题和技术。
2· 久经考验。该书于1990年首次出版，目前已是第三版，第四版正在进行中(注: 已经出版)。
3· 严格。在数学上是严格的。一些性质留作练习（我们必须给学生一些事情做），但我们在数学上不遗余力。 （诚然，一些读者觉得数学令人厌烦。重点是我们支持我们的主张，而不是指指点点。）
4· 价格。您不会以如此低的价格找到许多1300+页的精装教科书。
5· 负重训练。随身携带算法简介可以增强你的肌肉。
好吧，第5条是个玩笑，但其他原因都是严肃且真实的。

We can easily make each of them run in time O  using ordinary binary heaps. By using Fibonacci heaps, Prim’s algorithm runs in time O(E+VlgV ), improves over the binary-heap implementation if |V| is much smaller than |E|.

HEAPSORT(A)
    1 BUILD-MAX-HEAP(A)
    2 fori=A. length downto 2
    3   exchange A[1] with A[i]
    4   A.heap-size= A.heap-size-1
    5   MAX-HEAPIFY(A, 1)
图6-4给出了一个在 HIEAPSORT的第1行建立初始最大堆之后,堆排序操作的一个例子图6-4显示了第2~5行for循环第一次迭代开始前最大堆的情况和每一次送代之后最大堆的情况HEAPSORT过程的时间复杂度是O(nlgn),因为每次调用 BUILD-MAX- HEAP的时间复杂度是O(n),而nー1次调用MAX- HIEAPIEY,每次的时间为O(lgn)。

在程序的每一步中，从A[i]、 A[LEFT(i)和A[RIGHT(i)]中选出最大的，并将其下标存储在largest中。如果A[i]是最大，那么以i为结点的子树已经是最大堆，程序结束。否则，最大元素是的某个孩子结点，则交换[i]和原来的A[largest]的值。从而使i及其孩子都满足最大堆的性质。在交換，下标为 largest的结点的值是原来的A[i]，于是以该结点为根的子树又有可能会违反最大堆的性质。因此，需要对该子递归调用MAX- HEAPIFY。

divide-and-conquer algorithms partition the problem into disjoint subproblems,
solve the subproblems recursively, and then combine their solutions to solve
the original problem. In contrast, dynamic programming applies when the subproblems
overlap—that is, when subproblems share subsubproblems.

所谓算法，就是良好定义的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。

For
most of this book, we shall assume a generic one-processor, random-access machine (RAM)
model of computation as our implementation technology and understand that our algorithms
will be implemented as computer programs. In the RAM model, instructions are executed one
after another, with no concurrent operations.

INSERTION-SORT(A) cost times
1 for j ← 2 to length[A] c1 n ##这个不是N-1吗？？？？？？？？？？？？？？？？？？
2 do key ← A[j] c2 n - 1
3 ▹ Insert A[j] into the sorted
sequence A[1  j - 1]. 0 n - 1
4 i ← j - 1 c4 n - 1
5 while i > 0 and A[i] > key c5
6 do A[i + 1] ← A[i] c6
7 i ← i - 1 c7
8 A[i + 1] ← key c8 n - 1

The bug in the argument is that the "constant" hidden by the "big-oh" grows with n and thus is
not constant. We have not shown that the same constant works for all n.

The ratio of the (k + 1)st and kth terms in this series is k/(k + 1) < 1, but the series is not
bounded by a decreasing geometric series. To bound a series by a geometric series, one must
show that there is an r < 1, which is a constant, such that the ratio of all pairs of consecutive
terms never exceeds r. In the harmonic series, no such r exists because the ratio becomes
arbitrarily close to 1.

The total number of levels of the "recursion tree" in Figure 2.5 is lg n + 1. This fact is easily
seen by an informal inductive argument. The base case occurs when n = 1, in which case there
is only one level. Since lg 1 = 0, we have that lg n + 1 gives the correct number of levels.
Now assume as an inductive hypothesis that the number of levels of a recursion tree for 2i
nodes is lg 2i + 1 = i + 1 (since for any value of i, we have that lg 2i = i). Because we are
assuming that the original input size is a power of 2, the next input size to consider is 2i+1. A
tree with 2i+1 nodes has one more level than a tree of 2i nodes, and so the total number of
levels is (i + 1) + 1 = lg 2i+1 + 1.

我对《算法导论CLRS》的态度一直是有所保留的。虽然早在国内的时候，这本书一直被推崇为经典。但我那时就觉得它对算法的描述不好。一段费解的伪码，加上一大段费口舌的解释。我觉得本可以做得更好。  后来知道，这是典型的美国本科生用书，美国的本科教材，大抵很罗嗦，都是厚...

有保留的推荐

这篇书评可能有关键情节透露

                        我已经看完《算法导论》很久了，不接触算法也很久了。也没有《算法导论》的习题解答。 容我先吼一句：孩子，醒醒吧，那都是骗人的！！！ 老子都看完算法导论了，还不是一样做着前端的外包，还不是合同到期直接滚了。。。算法酷炫一点有什么用，比大数据部门的一部分人厉害又有...

99%的题目完成度  楼主黑化的不归路  附带学习心得

我读算法导论的目标： 书上的内容全部看懂（附录除外，已经为这些基础知识专门看了一大厚本的《离 散数学》，所以只看了几道从前没思考过的题，），习题(excersice)和每章末的 思考题(problem)全部尝试独立完成，即使不能做出，也一定要从网上找到答案。  实际完成的内容： 书...

从头到尾读完了,想说的绝不止这些

之前尝试自学这本书，很失败。。太难。。 后来到美国上学开始系统的跟着老师走这本书。基本看完了，也写写评论。 首先我肯定是力荐的，经典。 然后几个问题：  1. 初学者，自学? 第一次看之前，我大概过了一遍MIT公开课，看了Data Structure and Algorithms in C++ (大概这个名...

希望评论的人能基本看完再评论

《算法导论》在我心目中的地位无疑是最高的。  第一次读到这个书，大约是在高一的时候。很荣幸地读到了南京大学翻译的《算法导论》第一版，名字叫《现代计算机常用数据结构和算法》。1994年出版，当时在国内是非常先进的译著。因为几乎是填补空白的作品，其中的诸多翻译处理得...

跨越时代的罗盘

这本书和国内学者编写的算法教材有些差别。  首先，就像其他国外教材一样，该书讲解的很细致，习惯国内教材的读者可能觉得写得有点罗嗦，不过个人感觉很适合自学。  其次，每一章节最后都附有延伸阅读的建议，对于深入学习很有帮助。  最后，本书对算法的讲解使用的是伪码，不...

不容易看，但值得看

去年，我曾借阅过这本《算法导论》，读《算法导论》时常有这种想法：当读到一章比较难懂的部分，如大段的数学证明，或者题目很难做，这个时候就会没耐心去读，或者草草带过，不求甚解，有时干脆跳过不读～但又心存愧意，觉得碰到晦涩难懂的就不去钻研而选择逃避，实在不该。于...

读书感悟

我自己花了3个月差4天的业余时间读了大约575页，最后一个章节 selected topics 略过了，后面的 appendix 也略过了，前面二十六章略过了几个小节，个人觉得无伤大雅的地方。 体会就是，确实不错。比较注重算法证明和逻辑推导，某种程度上更像是在读数学教材，但是所需要的数学知...

所有习题的答案

这本书一直是公认的算法学习的经典，但不知道是翻译原因还是自己当时火候不够，在大一初学算法的时候这本书我没看得太懂。反而是一本用C++描述的数据结构的书让我对数据结构和算法入了门。  不过后来看了MIT OpenCourse中这门课的录像，才认识到这本书的深度和精确性。结合MIT...

码农必备锄具

这篇书评可能有关键情节透露

                        很不幸，我在看第一章的时候就看到了两个苍蝇：  第一个：an algorithm is any well-deﬁned computational procedure。 翻译：算法就是任何良定义的计算过程。 问题：well-defined翻译成“良定义”。多么好的翻译啊！！！ Google翻译都能翻译为“明确定义的”，大家可以去试...

特别写给中文版-求翻译给力

这篇书评可能有关键情节透露

                        https://github.com/ssjssh/algorithm 反之我这么干了，现在已经到第八章，比较重要的算法一个不差全部用Python实现了。我用Python的主要目的就是即想要伪码的易读性，又可以真实的执行。鉴于很多地方使用了Python的list作为数组使用，这个是有问题的，因为Python的list是链表...

有没有人实现算法导论里面的算法？

记得小学时，有很长一段时间疯狂的迷霍金，四年级的寒假拿了一百块压岁钱去买了两本他的科普读物《时间简史》《果壳中的宇宙》，一本45一本42，虽说是科普读物且全书只有一个数学公式（E=MC²），当时仍然完全看不懂，只能看看画，但附赠书签里的一句话却让我印象深刻：阅读...

一种非廉价的快乐

描述算法的这种书翻译一旦有错误，或者意思表达不到位，看起来就很吃力了。  第一次看算法导论是看的中文版。我是从头开始看的，一直看到图算法结束。读的时候主要追求速度，不少地方看的不是很明白。然而有些地方我觉得是翻译的问题导致理解上的障碍。  china-pub 上有人指出...

关于这本书的翻译

感觉翻译没传说中的烂，甚至可以说在我看过的翻译书中算好了，不过还是英文对着看的，怕哪里漏了。 其实本书在有了一定数学基础来说(至少离散概率论微积分基础掌握的较好，如果运筹学组合学图论也看过就更好了，我当时差不多是都看过一两本入门书的水平)，看起来是很快的，我之...

数学基础较好的还是挺容易看的

如果你觉得TAOCP太厚了，那就读这本。虽然比起很多计算机算法书籍，这本书也是很厚的，它的确值得这么厚。 读了这本书，基本上就不需要再读其他的算法教科书了。

学计算机科学不可不读

这篇书评可能有关键情节透露

                        2022年4月 《算法导论》第4版发布！！ 用的是金色封面。同时第4版给大家准备了一份极为丰厚的礼物，也就是全书算法的Python代码，并附有测试。  （私信我得电子书和每章答案） 这本书是经典，要精读多遍，所以强烈推荐用纸质书。 大概1000元可以买到！！ https://mitpress.mit....

官方配套了python源码实现  还有每章的答案

如觉得难建议先修Mathematics for Computer Science  18.062J	Mathematics for Computer Science	Undergraduate  http://book.douban.com/subject/20472991/

如觉得难建议先修Mathematics for Computer Science

算法的核心思想总是会以数学抽象表现，而这本书给人感觉就是数学对象太多，少了程序的思维，有些方法编写技巧也被忽略了，还有就是里面用伪代码描述的很多算法复杂度都是很高的。      过多的强调了算法的正确性，而不是实战性质，而且都是Introduction，更多的还要看其参考...