这本书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

    注意:本书有一定的难度,需要有基础的同学才能看下去

    附带豆瓣的评论供参考:


    作者:BAY(来自豆瓣)

    我已经看完《算法导论》很久了,不接触算法也很久了。也没有《算法导论》的习题解答。

    容我先吼一句:孩子,醒醒吧,那都是骗人的!!!

    老子都看完算法导论了,还不是一样做着前端的外包,还不是合同到期直接滚了。。。算法酷炫一点有什么用,比大数据部门的一部分人厉害又有什么用,还不是个被裁的命!!!

    ———————————————吼完,舒坦多了—————————————————

    ——————————————以下是楼主黑化史————————————————-

    今年5月21日

    实习期,同事的一句玩笑话促成了我买下这本《算法导论》。过了今晚,正好算半年吧。

    回顾一下:经过半年的努力,我基本算是读完了算法导论。全书除掉附录和索引,全部看完,题目一共1115道,一共有8道题算是没有完成。。。8道里面有2道是概念不懂,比如34.5-2,那个“一元形式”我就没看懂。。还有3道是结论和题设不一样,如35-6的d小题,感觉是S和T写反了。。还有3道是自己没有做出来,也没时间做了,分布在第28章的第二个小节的附带小题目中。。因为我再过一个月就要失业了,不能再陪那几题耗下去了,明天开始复习一下设计模式,ios代码,数据库之类的。。。综合下来完成度在99%以上吧。。

    刚开始我受了网络评论以及自己内心的怂恿,以为看完这本书就能飞上枝头变凤凰,毅然决然地边工作,边每晚10~12点半,以及周六日无休看这本书。。。开始的那一两个月满是激情,因为今年本科毕业,5,6月份是实习,那个激情的,自己赚钱啦,白天工程代码,晚上科学算法,太完美了。。

    但从7月份开始我开始黑化,因为,公司部门调整,我的部门要没了,部门的老员工陆续离职,因为本身也就是干外包的,再加上本人是前端,再加上,我这个刚毕业就要失业。。。幸亏部门的外包合同是到年底,给了我一点喘息的机会,至少到年底才裁员。。哈哈,我加快了脚步看这本书。。。不过内心已经开始黑化。

    到了10月份以后,由于离被裁的时间越来越近,部门的有点本事的老员工也走的差不多了,就剩下几个老弱病残和我这类刚毕业的小苗子。。应付着外包的合同。。。我已经不在乎自己能不能变成凤凰了,只希望善始善终,给自己一个装B的理由。。于是继续攻打着后面的那些变态章节。

    昨天终于算看的差不多了,能做的部分基本都做了,少部分遗留题目,我也就只能算了。。我去买了本设计模式的书看一看,希望能够,裁了后找个月薪不比现在外包低的岗位,八千以上最好。。。

    不过这本书最大的好处就是能够让我装B,想着,那些同一楼层的高学历大数据员工,鄙视我们这些本科外包人员时,我能够回击他们,能够在算法上虐他们中的一部分。。。我被裁时,能够吼一句:“你们这些渣渣,水平都没有我高,竟然敢瞧不起我,渣渣,裁了我是你们的损失”。。。。哈哈,想想还有点小激动呢。。。

    要是看着MIT这个名号,老子纯自学,花了半年就干的差不多了,老子要是有命去MIT,将来也是大神。。。。各种YY。

    至此,楼主彻底黑化。

    —————————————-关于楼主的能力—————————————————

    本科毕业,大学的《离散数学》,《高等数学》《线性代数》,都是一般般的分数,

    大学时,愤青,没本事却高傲指责国内教育,然后看了本《什么是数学》平衡心理。算法导论之前,上过《数据结构》这个课,然后,在POJ做了两个月的ACM入门题。。。然后学了一些java,包括《30天自制操作系统》以及《JAVA编程思想》。。当然工作需要的IOS的一点OC代码。。。也算有一定的代码量。

    —————————————-正能量PS:学习心得——————————————

    下面是本人在知乎的一个回答,完善版本:

    0.孩子醒醒吧,我看完了还不是个外包被裁员的命。。

    1.英文版和中文版的差别不大,算法导论的翻译绝对是可以的,当然的确有部分明显的错误,不过基本都是非常明显的打印错误,少部分的翻译错误也是很容易判别的,绝对不会影响阅读。。。如果你中文版看不懂,那么基本看英文也是一个结果,该不懂的还是不懂,某些人可能是因为中文版没看懂,然后断定中文版翻译有问题,这样就可以掩盖自己的水平缺陷,达到自欺欺人的效果。。。占比很小的翻译错误可以临时对照pdf的英文版。。。。。总之,没有必要特意看英文版。。。

    2.没有算法基础的同学,尤其是连数组,堆栈,二叉树的遍历,几个基本排序算法的代码都写不出来的同学,别看这本书。。。虽然这本书也会提这些东西,但是,它基本是做个引子,然后引入更深的东西。。。就好比,小学数学没学好,直接去学大学数学一样。。。所以先从小学数学学起(先学一本最基础的数据结构)。

    3.如果浏览目录发现一半以上的东西是完全没见过的,那么在第2条的基础上,去poj练一两个月,把网络流的基本算法步骤,凸包,并查集,线段树,贪心动态规划,逆序数,以及基本的数论算法之类的东西给补上。。。不然就好比,高中毕业的你直接看《苔丝》之类的英文小说一样,一段话里面有二三十个单词不认识,临时去查,去标记,特别痛苦。。根本享受不了小说的气氛和韵味。

    4.在做好2.3的基础上,如果乐于探究算法的原理,想知其然并知其所以然,而且又有很多时间(几百个小时吧),这样就可以读这本书了。。我读这本书的证明部分是有个比较独特方法:不要把自己当成一个读者,而是一个交流者,和这本书的作者(大师)交流。。比如,它一般是要在做一个大证明之前会先抛出这个证明结论,你看到结论后,如果比较感兴趣,可以先自己试着去探索一下,证明一下,探索几十分钟后,哪怕没有探索出结果,那也是多少有了自己的一点收获,然后带着你的收获再来看这本书的证明,就像你和大师交流一样。。。

    5.别把这本书做入门书,说是入门书的人要么就是特别厉害而且特别不负责任的,要么就是啥都不懂的人以为看到“导论”两个字就认为特别基础的人。

    6.关于数学,首先必须是大学毕业的,学过高等数学,矩阵和离散数学的,如果没学过这几本,那么里面的东西也真够呛,原因同2。。如果学过但是忘了,那么书的附录部分会有复习,看一下就可以了。。。如果看了还是搞不懂书里面的推理,那么基本就是你可能不太适合读这类书的证明部分,不太适合搞研究。。。仅此而已。。。

    7.要想完成度比较高的话,还需要不怕死的精神。比如那个斐波那契堆,vEB树,网络流的证明部分,还有NP那一章节的证明,看着特别唬人,其实只要不怕死,硬着头皮一行一行啃,其实也能过,而且后面的题目却不算难。。。

    8.小马过河的典型案例,小马过河,在硬是“不走桥”这个前提下。算法导论很有这个意味。。。老牛说比较浅,松鼠说很深,真正我自己淌过去的时候才发现不是很深也不是很浅。。。。。。想起大学的日语N1的高分之日,以及托业900的笑傲之时,都一样的。。。

    9 .算法导论本身内部有很多明的或者暗的承接关系,明显的证明之间互相引用的承接关系我就不讲了,暗的承接关系比较有意思。比如12章开始,二叉树是2叉的东西,13章补充,14章扩张,之后18章是若干叉的B树,19章的logN叉,20章的√N叉,之后习题中补充了n的1/3叉,等等。。1叉就是链表,而N叉就是数组和最初的第10章相对。。。

    比如还有一条是斐波那契数,4-4那一题就讲了点。。16章的动态规划的两个思路。19章的斐波那契堆又讲了点,后面的31-3又结合数论讲了些,如果再结合30-1的那题,以及31.1那章节之前的扯淡部分的内容,还能优化。。看了第27章后啥循环都想写成动态多线程的,再优化一次。无穷无尽了。

    10 . 对于翻译的补充,12.3-5坑了我好久,严重翻译错误。21.4的讲解里“一个增长非常慢的函数与其增长非常慢的逆函数”,也是一个非常屌的错误。。还有第33章末尾的注记里面,那个“指南针和尺子”作图,也是亮瞎了我的眼。。

      1. 有一些题目真的不是努力就可以的,有时还需要灵感,也就是书前言说的创造力。。比如5.1-3。。。很有意思的东西,想出来时,贝叶斯,灵光一闪。。哈哈。装B必备。
      1. 读到后面整个人会进入一种奇妙状态,比如读到最短路径,网络流那一章,闭上眼睛整个脑子里就有那些网络啊,流动啊,那个预流就好像一个海湾里一个浪打出去,挤着出湾口出去,没出去的,就被礁石挡回来,来回激荡。。而floyd_warshall就好像一把小石子丢到一个平静的池塘里,千万小涟漪同时向外扩散。。。而负权环,就算是池塘有个无底洞,有个塌陷的大漩涡吧。。。

    还有网络流的证明部分,那个最小割和最大流,后面线性规划,也是,两种相辅相成的东西。。镜像一般,一实一虚,虚到实,实到虚,虚实结合。。。好奇妙。。。还有FFT那个美丽的蝴蝶,,等等

    有一回在动车上,我在看书,别人问:“你看这些公式怎么不用草稿纸啊。”我回了句:“你知道盲棋吗?”有好多题,其实就是一个比较感性的想法,然后,哈哈,当然不用草稿纸,理性的推理也能建立在感性的想法上,重要的是想法。

    后来看附录矩阵部分时,也基本是直接在脑子里完成了递归证明,当时感觉自己屌爆了,么么大。

    1. 本人读算法导论时,直接事先在微信朋友圈喊了一句,说要单枪匹马干掉,,然后每个周六都有进展就直播,当我遇到苦难,郁闷地去刷朋友圈时,哈哈,当初那个状态,还有萌妹子点赞呢,瞬间,满血满蓝回归了。。当然,好多时候,脑子会过热,这个时候,冷却与放纵是必须的。

    14 本人是双子座,思维跳跃,性格分裂,所以评论也就跳跃与分裂了,哈哈。

    ————————————补充分割线———————————————-

    跟评论的人吵起来了。。也是,毕竟这篇满满的负能量嘲讽,阿Q文章,自然会让不少人不满。。算法导论本身也就是一个不上不下的书,说研究性,大数据的那些数据挖掘的博士们可瞧不上这本呢,说工程性,hadoop的工程师们可瞧不起这本呢。说竞赛性,那些ACM国际大奖的人可瞧不起这本呢。

    可能某些话不慎得罪了某些人,想想,打了阿Q的某些人如果听到,阿Q说:“儿子打老子”之后,一定还会回来补一拳吧。

    我曾经给自己保证过,我哪天真的读完了算法导论,我可以昂首挺胸的离开那家裁我的公司。我做到了。

    我现在真觉得我可以在算法部分“虐大数据部门的某些人”,我真这么觉得。。。这本书的知识现在只是我算法能力的一个真子集。读完后的这两个月,我每天仍然都在变强。

    ———————————-补充分割线—————————————————-

    下面回复中有不少人关心我的状况,我很菜以至于很多事情都无能为力。这曾经只是个童话而已。

    算法算是彻底和我无缘了。

    真想找个方向一直干下去,奈何造化弄人,我这一年因为工作的安排,写了下go的并发调度,写了python的爬虫,还搞了点ES。。。毕竟菜,低人一等,只能都答应下来。

    算法导论多少还是帮助了我吧,至少我在分析性能相关的模块的时候会更加理性,更加实事求是。。

    因为做了一件别人眼里不容易的事情,所以,后面工作胆子就比较大,先喊出来再去做,比如去看个go的运行时然后获取灵感加入到并发调度中,或者去突击下ES和lucene源码写个parser的plugin之类的。。。整个人放的比较开,敢做事,敢做成事,比较有韧性。。。虽然级别还是很低,年限也很低。。。有时自我安慰(吹牛):干一样的活,拿半份工资。诶。。。

    ———————————-2018年4月7日补充分割线—————————————————

    来北京4年多了。我也终于追过了大厂应届的白菜价。算法导论的那段经历仍然是我最纯真最珍惜的技术经历。。。它让我有了一个在职场无论遇到谁都不惧怕的基础算法理解。。。它让我明白如何去单挑一个比自己强很多的东西。那就是死磕,就是的吃饭睡觉都去死磕,不断地在不同场景切换时,放空自己后回过来思考、实验。

    或许是一直小公司小部门的经历,我发现,比起算法,业务更加重要。算法只是业务实现的很小的一环而已。。。考虑整个业务,考虑算法在业务中的地位,考虑业务里面的商务,技术,前端,后端,运营的每一环。。。考虑产品的迭代,整个节奏。。。虽然依然是个小兵,但这种感觉真的很不错。


    我读算法导论的目标:

    书上的内容全部看懂(附录除外,已经为这些基础知识专门看了一大厚本的《离

    散数学》,所以只看了几道从前没思考过的题,),习题(excersice)和每章末的

    思考题(problem)全部尝试独立完成,即使不能做出,也一定要从网上找到答案。

    实际完成的内容:

    书上内容全部看完且看懂(当然看了很长时间,不免有些内容忘记了)。习题和

    思考题基本全部完成,所有没有完成的题目(自己不会做,并且也没找到答案)一

    共35个。算来平均每章一个。看着写满两大本的题解,心里还是很有成就感的

    (尽管我女朋友说:“你写这些,有什么用啊?!”)

    这一年零8八个月的时间我都干了什么?

    一口气读《算法导论》到第30章,前26章的题基本做了,觉得实在有点累,调剂

    一下,转而攻读MIT的另一本名著《计算机程序的构造和解释——Structure and

    Interpretation of Computer Programs》,几个月后重披战甲,从27章开始看

    完了全部的《算法导论》,并将最后9章题目做完。由于看得细,而且还有其他

    事情要做,前后拖了20个月,总算看完了,真的很累。

    我的书评:

    踏踏实实看完书,仔仔细细的思考每一道题,即使不会做,至少读过,思考过,

    可能未来的某一时刻你的脑海里突然就有了灵感。

    为什么我的书评只有一句话(而且似乎也没有评价)?

    说真的,我作为一个小小的学生,真的没有资格评判人家大牛用十几年汉水和智

    慧来增删,校对,实践,研究得来的一本著作。如果有什么不好的印象,那只能

    说是没到那个境界,理解不了,不能吃不着葡萄说葡萄酸,反而批评人家。

    有心人从我上面的一大段废话和短短的一句似是非是的书评,也绝对可以看出来

    这本书的卓越之处:

    (1)深入浅出:能耗费一个人20个月的时间去看,可见这本书绝非一朝一夕的快

    餐,要知道即使是世界上最一流的大学,利用一年的课程去讲算法课,也只能挑

    本书的部分章节去讲而不能完全覆盖。既然题目能做出绝大多数,证明只要你用

    心,这本书的难度完全是可以承受的,决不会让你有无从下手的感觉。

    (2)情节生动有趣:对,没错,我就是要像形容小说一样形容这本书,不然我绝

    不可能坚持看这么久。但是比小说有趣的是,故事里人物的命运是作者安排的,

    你或喜或悲总是被人牵着走,而这本书却是让你作主角去打开一扇又一扇通往未

    知的大门,解开一道又一道的难题。

    (3)既连贯又独立:不同章节既独立完备又内在高度相关。即使你专注于某一个领

    域,我认为这本书给你的介绍也是很充实的,而且可以直接看,这就是为什么我

    中间放下一段时间后又可以从新拿起来读而不用重新来过。当然个章节间内有一

    个东西是一脉相承的,那就是:(程序运行的理论)效率。从头到尾看得到的绝

    对比单独对待每一章得到的价值的总和大得多。

    (4, 5, 6, …)余音绕梁:老子说:三生万物。我只说三条,万就留待你自己去

    挖掘,也留待你从书中找到精彩的答案。

    祝读此文者也能享受一趟与《算法导论》的精彩的马拉松之旅。