微信号:programmer_club

介绍:程序员第一自媒体,与你探讨码农人生路上遇到的各类泛技术话题,定期为你推荐码农人生思考、感悟以及启迪!

如何学算法?

2015-10-12 21:05 程序员之家

来自:知乎

链接:http://www.zhihu.com/question/19981544


回答者:某小白,Android码农


建议千万不要一开始就看《算法导论》,这本书有太多关于算法的数学证明(如果你喜欢这种,那么你就看这本)


我强烈推荐你看看这本:算法(第4版) (豆瓣),作者是高德纳的学生:塞奇威克 (Robert Sedgewick)


去年我在准备校招面试的时候偶然发现这本书,我越看越着迷,书中算法代码主要是用Java编写,里面有大量的图来让你明白例如:排序,查找,树和图的算法运行过程。


这本书的目录编排也很清晰,他就告诉你算法主要就可以分为:排序,查找,图和字符串。从这4个方面可以演化出很多算法。


我觉得最关键是:这本书的作者不但是在告诉你what,而且告诉你why(分析各种算法的优缺点)


----------------


补充一些我觉得这本书好的地方


比如讲到快速排序,很多书可能讲了快速排序的原理就完了。但这本书就直接讲了原始的快速排序可以改进的地方:1. 在小数组上,切换到插入排序;2. 三取样切分;3. 三向切分的快速排序。


优先队列怎么和排序算法扯上关系呢?其实优先队列就是可以用堆排序来实现,堆排序的时间复杂度和快速排序是一样的,但是实际中为什么堆排序的运行时间要比快速排序多呢?因为这和CPU的Cache命中率有关系,堆排序不符合算法运行的局部性原则


还比如书中2.5节,讲了排序算法的实际用途。


这本书不光告诉你算法的原理,还告诉你算法的用途。




回答者:李四,CS@THU


看《算法导论》,重复看。在略过复杂度摊还分析的情况下,初中数学基础足够弄明白绝大部分内容了。


同样推荐的还有《数据结构与算法分析》,以及邓俊辉老师的MOOC课程《数据结构》。


算法导论这本书,从初三到高二,自己断断续续的看了三年时间。对于算法导论,自己的阅读路径比较曲折艰难,这是当时自己只有中学基础的缘故。好在算法导论 偏向于培养构造性的思维,解题、证明技巧是“算法的方式”而非“数学的方式”,因而得以勉强读了下来。不过平摊分析这样的部分就无能为力了,选择跳过。


1、循环不变式是算导最开端的内容,也是算法正确性证明最重要的钥匙。本质上,循环不变式是算法归纳证明的形式化。理解算导中每个算法循环不变式的证明过程,就是在理解算法的运行原理。


2、算导阅读不需要很深的知识储备(你看我这样的初中生也能勉强看)。在看高斯消元LUP分解的时候,我只是通过附录补习了一下矩阵的基本知识,然后就可以看前面的LUP分解算法了。理解算法的正确性是相对容易的,理解算法设计的精妙,反推算法设计的过程难之又难。


3、代码实现是最好的学习过程。因为竞赛的缘故我使用的是c,当然你也可以用python、java或者brainf**k(雾)。啃完二十多页的二项堆,并且 敲出代码成功运行后,当时的我崩溃的发现还有三十多页的Fibonacci堆在后面等着我。为了记住Fibonacci堆的设计细节,我重复写了20多遍 以至于闭着眼睛都能写出来,结果发现在竞赛中根本用不到,我们有好用又好写的Pairing heap。尽管如此,Fibonacci堆的证明简单而直观,算法设计有趣得很。


4、尝试修改优化算法导论上的代码。在编写线性规划单纯性 的代码时,我发觉(n+m)*(n+m)的矩阵异常浪费,稍作思考发现可以改成n*m的矩阵加上几个附加向量信息;进一步,对全幺模的情况,可以使用稀疏 矩阵常见的优化方法——链表替代行向量。几个优化过后,我终于可以在竞赛允许的时间、空间、编码量内写一个非多项式的线性规划单纯形算法了。


5、快 速傅里叶变换也是个有趣的例子。我们都知道,快速傅里叶变换的计算是在复数域上的,而计算机中复数的数值精度会导致FFT在向量比较长的时候丢失信息。后 来学过数论部分,发现复数域是可以由一些特定的模整数运算取代的,于是FFT就可以被用来加速高精度乘法。再后来,发觉这个方法叫做快速数论变换。


6、每一章的课后习题是检验本章内容是否掌握的准则。如果课后习题有二分之一以上无法独立解决,不妨重新阅读本章内容,给深入思考留些时间。结合习题阅读章节也是可行的。(我记得网上可以搜到部分章节的答案)


7、说到底,算法导论只是本基础教材,其中无论数据结构、图论,还是动态规划,贪心算法,都只是基础内容。如果看不懂,你需要重新看一下这一章;如果一直看不懂,你需要重新从头读这本书;如果你发觉能看懂了,说明通过培养,你习得了构造性的、“算法”的思考能力。


原回答:你是如何坚持读完《算法导论》这本书的? - 李四的回答


回答者:蔡陪陪,太天真太认真


我第一次学算法直接看《算法导论》,结果信心大受打击。后来发现Robert Sedgewick在Coursera上出了一系列算法视频教程,把一个算法以动画的形式展现出来,非常适合新手。课程名字就叫Algorithm,普林斯顿大学的,分为Part 1和Part 2。


看视频一边看一边做笔记,看完一个单元跟着把代码写一遍。看完整个教程之后把所有算法都默写一遍,忘记的算法复习一遍。就酱。



回答者:HUI SONG,友善度什么的真垃圾!!


不知道你学算法是为什么,目的不同,学法不同侧重不同。


可能性1: 如果你对算法理论和精髓感兴趣,数学推理能力也不错,不急着看完刷题接面试抢offer,你可以去仔细研究下《算法导论》。


可能性2:如果你和我一样,半路出家,时间紧迫,看书看不进去,你可以试着看视频。


我当年看的是princeton的算法公开课。刷一遍视频,有了基本的感觉,去刷题。



以面世为目的,我用的“cracking the coding interview”,题目是按照array, stack&queue, 链表,树图,递归这种章节安排的,每章节题目7-8个,不多,难度中等,找感觉很有帮助。第一遍自己写不出来的话(我就是,这么弱!),画图分析,抄背默。一遍做完再做一遍,第二遍就快很多,理解也深刻了,所谓读书百遍,其意自现,算法也一样。



刷完这些有点信心了,就去leedcode上给自己浇浇冷水,看看面经。
这些都做完了,你就等着点钱选offer吧,算法学的好不好你早不在乎了,因为你会用了。


(鄙人也觉得上来就推荐《算法导论》的,不是大大牛就是装13!!!)



回答者:姚冬,程序员


推荐我的一位朋友写的 Book of Elementary Algorithms and Data structures 《初等算法》


虽然书是用英文写的,但我这位朋友是中国人,正式的工作是软件工程师和项目经理,业余时间对算法很有兴趣,他花了数年时间,把自己对算法的心得体会写成了这本书,把全部的内容以及相关源代码都开源了。


他对算法和编程语言有深入的研究,能熟练使用十余种编程语言。这本书中的算法的参考实现都提供了 C, C++, Haskell, Python, Scheme/Lisp的版本。


项目开源:


liuxinyu95/AlgoXY · GitHub


这本书还在持续更新中,几天前还有修改。


下面的引用来自他正式发布本书时写的一篇blog,这是我认识的最有情怀的程序员了。


参考:

有两本书对《初等算法》影响最大。一本是Chris Okasaki的《Purely functional data structure》另外一本是《算法导论》。写作过程中还参考了一些其他书籍,包括Knuth的《计算机程序设计艺术》,Richard Bird的《Pearls of functional algorithm design》,Bentley的《编程珠玑》以及一些论文。


不足:

写这本书的六年中,我总是想起法国数学天才伽罗瓦最后写的那句话:“我没有时间了!”,我原计划用10年写完这本书,结果提前了4年。这样的代价 很大。为了避免翻译,过滤“噪声”,我直接用英文写作。由于不是native speaker,书中的英文语法和拼写难免贻笑大方。为了赶时间,proof reading被压缩,许多结论采取了“拿来主义”,没有进行严格的数学证明。一些章节的课后习题也没有给出答案。


未来:

理想情况下,一本严肃的算法书应该在稳定、宽松的环境下精雕细琢。可是在社会剧烈发展的今天,在日新月异的中国,在人们习惯快餐而不再享受大餐的 快节奏生活中,在微博、微信取代文章、书信的手机网络大潮下,这样的理想环境根本不存在。未来不可预知。对于《初等算法》这本书,开放给社区是最好的选择。需要做的工作很多:

* 翻译中文版

* 社区proof reading和review,修正内容上的错误和英文上的不足

* 提供一本习题集

* 补足数学证明

* 采用强大的数学工具,对形式化的算法进行分析


一些数据:

《初等算法》黄金分割0.618版本,历时6年,在github上总共提交1680次commit。全书600多页,19万字(word)。2万2千行示例代码。


保护:

《初等算法》在GNU FDL许可协议下发布,所有代码在GNU GPLv3协议下发布。



回答者:王焱,喜欢写东西


楼上觉得直接啃很难的。


其实,有一个办法,MIT有这门课的公开课,百度搜索 MIT:算法导论,课本就是算法导论,一边看一边认真完成这门课的课后题。


一定不要小看这些课后题,往往是很多算法的关键所在,理解了这些课后题,你才能够说真正的懂了这个算法,只是会写代码根本不算学会。

这是一个挺不错的办法。


自己学没有任何指导的话,的确会有一些困难。当年自己啃的时候,不注意方法,直接硬啃,直接把书都给翻旧了,还是没有学好。哎,都是血泪呀。。


而如果你一边看课程,一边学,还觉得艰难的话。我真的觉得,你需要想办法提高下自己的数学能力了。


你要算法入门的话,算法导论的确是本好书。它的知识点覆盖面,框架的确没的说。



点击【阅读原文】,体验100offer

 
程序员之家 更多文章 我们这一代人的困惑 神剪辑,揭秘程序员加班内幕,不能看,看完想笑又想哭! 美国12位创新型程序员:让科技永远改变 说说怎么写clean code 500,000+年薪程序猿出身哪里 猎聘网揭秘前十大学校
猜您喜欢 10个小故事,让思维拐个弯 精:你的经验正在蒙蔽你的双眼 CSDN已推出30多个知识库 你所关注的技术领域在其中吗? 褚霸:阿里云数据库要放大招! 公开课回顾 | 零基础小白如何学会写第一个爬虫