算法图解.pdf
《算法图解.pdf》由会员分享,可在线阅读,更多相关《算法图解.pdf(197页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 内 容 提 要 本书示例丰富,图文并茂,以简明易懂的方式阐释了算法,旨在帮助程序员在日常项目中更好地利用 算法为软件开发助力。前三章介绍算法基础,包括二分查找、大 O 表示法、两种基本的数据结构以及递归 等。余下的篇幅将主要介绍应用广泛的算法,具体内容包括 : 面对具体问题时的解决技巧,比如何时采用 贪婪算法或动态规划 ; 散列表的应用 ; 图算法 ; K 最近邻算法。 本书适合所有程序员、计算机专业相关师生以及对算法感兴趣的读者。 定价:49.00元 读者服务热线:(010)51095186转600 印装质量热线:(010)81055316 反盗版热线:(010)81055315 广告经营
2、许可证:京东工商广字第 8052 号 著 美 Aditya Bhargava 译 袁国忠 责任编辑 朱 巍 执行编辑 贺子娟 责任印制 彭志环 人民邮电出版社出版发行 北京市丰台区成寿寺路11号 邮编 100164 电子邮件 315 网址 北京 印刷 开本:8001000 1/16 印张:12.25 字数:308千字2017年 3 月第 1 版 印数:1 4 000册2017年 3 月北京第 1 次印刷 著作权合同登记号 图字:01-2016-5339号 4 献 词 谨以此书献给我的父母、Sangeeta和Yogesh 前 言 1 1 2 3 4 5 8 10 13 9 6 7 12 11 前
3、 言 我因为爱好而踏入了编程殿堂。Visual Basic 6 for Dummies教会了我基础知识,接着我不断阅 读,学到的知识也越来越多,但对算法却始终没搞明白。至今我还记得购买第一本算法书后的情 景:我琢磨着目录,心想终于要把这些主题搞明白了。但那本书深奥难懂,看了几周后我就放弃 了。直到遇到一位优秀的算法教授后,我才认识到这些概念是多么地简单而优雅。 几年前,我撰写了第一篇图解式博文。我是视觉型学习者,对图解式写作风格钟爱有加。从 那时候起,我撰写了多篇介绍函数式编程、Git、机器学习和并发的图解式博文。顺便说一句, 刚开始我的写作水平很一般。诠释技术概念很难,设计出好的示例需要时间
4、,阐释难以理解的概 念也需要时间,因此很容易对难讲的内容一带而过。我本以为自己已经做得相当好了,直到有一 篇博文大受欢迎,有位同事却跑过来跟我说: “我读了你的博文,但还是没搞懂。 ”看来在写作方 面我要学习的还有很多。 在撰写这些博文期间,Manning出版社找到我,问我想不想编写一本图解式图书。事实证明, Manning出版社的编辑对如何诠释技术概念很在行,他们教会了我如何做。我编写本书的目的就 是要把难懂的技术主题说清楚,让这本算法书易于理解。与撰写第一篇博文时相比,我的写作水 平有了长足进步,但愿你也认为本书内容丰富、易于理解。 6 前 言 致 谢 感谢Manning出版社给我编写本书
5、的机会,并给予我极大的创作空间。感谢出版人Marjan Bace,感谢Mike Stephens领我入门,感谢Bert Bates教我如何写作,感谢Jennifer Stout的快速回复 以及大有帮助的编辑工作。 感谢Manning出版社的制作人员, 他们是Kevin Sullivan、 Mary Piergies、 Tiffany Taylor、Leslie Haimes以及其他幕后人员。另外,还要感谢阅读手稿并提出建议的众人, 他们是Karen Bensdon、 Rob Green、 Michael Hamrah、 Ozren Harlovic、 Colin Hastie、 Christo
6、pher Haupt、 Chuck Henderson、Pawel Kozlowski、Amit Lamba、Jean-Francois Morin、Robert Morrison、Sankar Ramanathan、Sander Rossel、Doug Sparling和Damien White。 感谢一路上向我伸出援手的人:Flaskhit游戏专区的各位教会了我如何编写代码;很多朋友 帮助审阅手稿、提出建议并让我尝试不同的诠释方式,其中包括Ben Vinegar、Karl Puzon、Alex Manning、Esther Chan、Anish Bhatt、Michael Glass、Ni
7、krad Mahdi、Charles Lee、Jared Friedman、 Hema Manickavasagam、Hari Raja、Murali Gudipati、Srinivas Varadan等;Gerry Brady教会了我算 法。还要深深地感谢算法方面的学者,如CLRS 、高德纳和Strang。我真的是站在了巨人的肩上。 感谢爸爸、妈妈、Priyanka和其他家庭成员,感谢你们一贯的支持。深深感谢妻子Maggie, 我们的面前还有很多艰难险阻,有些可不像周五晚上待在家里修改手稿那么简单。 最后,感谢所有试读本书的读者,还有在论坛上提供反馈的读者,你们让本书的质量更上了 一层楼。
8、算法导论四位作者的姓氏(Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein)首字 母缩写。译者注 关于本书 1 1 2 3 4 5 8 10 13 9 6 7 12 11 关于本书 本书易于理解,没有大跨度的思维跳跃,每次引入新概念时,都立即进行诠释,或者指出将 在什么地方进行诠释。核心概念都通过练习和反复诠释进行强化,以便你检验假设,跟上步伐。 书中使用示例来帮助理解。我的目标是让你轻松地理解这些概念,而不是让正文充斥各种符 号。我还认为,如果能够回忆起熟悉的情形,学习效果将达到最佳,而示例有助于唤醒记忆
9、。因 此,如果你要记住数组和链表(第2章)之间的差别,只要想想在电影院找座位就坐的情形。另 外,不怕你说我啰嗦,我是视觉型学习者,因此本书包含大量的图示。 本书内容是精挑细选的。没必要在一本书中介绍所有的排序算法,不然还要维基百科和可汗 学院做什么。书中介绍的所有算法都非常实用,对我从事的软件工程师的工作大有帮助,还可为 阅读更复杂的主题打下坚实的基础。祝你阅读愉快! 路线图 本书前三章将帮助你打好基础。 第1章:你将学习第一种实用算法二分查找;还将学习使用大O表示法分析算法的速 度。本书从始至终都将使用大O表示法来分析算法的速度。 第2章:你将学习两种基本的数据结构数组和链表。这两种数据结构
10、贯穿本书,它们 还被用来创建更高级的数据结构,如第5章介绍的散列表。 第3章:你将学习递归,一种被众多算法(如第4章介绍的快速排序)采用的实用技巧。 根据我的经验,大O表示法和递归对初学者来说颇具挑战性,因此介绍这些内容时我放慢了 脚步,花费的篇幅也较长。 余下的篇幅将介绍应用广泛的算法。 问题解决技巧:将在第4、8和9章介绍。遇到问题时,如果不确定该如何高效地解决,可 尝试分而治之(第4章)或动态规划(第9章) ;如果认识到根本就没有高效的解决方案, 可转而使用贪婪算法(第8章)来得到近似答案。 散列表:将在第5章介绍。散列表是一种很有用的数据结构,由键值对组成,如人名和电 2 关于本书 子
11、邮件地址或者用户名和密码。散列表的用途之大,再怎么强调都不过分。每当我需要 解决问题时,首先想到的两种方法是:可以使用散列表吗?可以使用图来建立模型吗? 图算法:将在第6、7章介绍。图是一种模拟网络的方法,这种网络包括人际关系网、公 路网、神经元网络或者任何一组连接。广度优先搜索(第6章)和狄克斯特拉算法(第7 章)计算网络中两点之间的最短距离,可用来计算两人之间的分隔度或前往目的地的最 短路径。 K最近邻算法(KNN) :将在第10章介绍。这是一种简单的机器学习算法,可用于创建推 荐系统、OCR引擎、预测股价或其他值(如“我们认为Adit会给这部电影打4星” )的系统, 以及对物件进行分类(
12、如“这个字母是Q” ) 。 接下来如何做:第11章概述了适合你进一步学习的10种算法。 如何阅读本书 本书的内容和排列顺序都经过了细心编排。如果你对某个主题感兴趣,直接跳到那里阅读即 可;否则就按顺序逐章阅读吧,因为它们都以之前介绍的内容为基础。 强烈建议你动手执行示例代码,这部分的重要性再怎么强调都不过分。可以原封不动地输入 代码,也可从 algorithms下载,再执行它们。这样,你记住的内容将多得多。 另外,建议你完成书中的练习。这些练习都很短,通常只需一两分钟就能完成,但有些可能 需要510分钟。这些练习有助于检查你的思路,以免偏离正道太远。 读者对象 本书适合任何具备编程基础并想理解
13、算法的人阅读。你可能面临一个编程问题,需要找一种 算法来实现解决方案,抑或你想知道哪些算法比较有用。下面列出了可能从本书获得很多帮助的 部分读者。 业余程序员 编程培训班学员 需要重温算法的计算机专业毕业生 对编程感兴趣的物理或数学等专业毕业生 代码约定和下载 本书所有的示例代码都是使用Python 2.7编写的。书中在列出代码时使用了等宽字体。有些 代码还进行了标注,旨在突出重要的概念。 关于本书 3 1 2 3 4 5 8 10 13 9 6 7 12 11 本书的示例代码可从出版社网站 我认为,如果能享受学习过程,就能获得最好的学习效果。请尽情地享受学习过程,动手运 行示例代码吧! 作者
14、在线 购买英文版的读者可免费访问Manning出版社管理的专用网络论坛,并可以评论本书、提出 技术性问题以及获得作者和其他读者的帮助。若要访问并订阅该论坛,可在浏览器的地址栏中输 入 哪些帮助以及讨论时应遵守的规则。 Manning出版社致力于为读者和作者提供能够深入交流的场所。然而,作者参与论坛讨论纯 属自愿,没有任何报酬,因此Manning出版社对其参与讨论的程度不做任何承诺。建议你向作者 提些有挑战性的问题,以免他失去参与讨论的兴趣!只要本书还在销售,你就能通过出版社的网 站访问作者在线论坛以及存档的讨论内容。 4 关于本书 目 录 1 2 3 4 5 6 7 8 9 10 11 12
15、13 14 15 16 18 17 目 录 第 1 章 算法简介 . 1 1.1 引言 . 1 1.1.1 性能方面 . 1 1.1.2 问题解决技巧 . 2 1.2 二分查找 . 2 1.2.1 更佳的查找方式 . 4 1.2.2 运行时间 . 8 1.3 大 O 表示法 . 8 1.3.1 算法的运行时间以不同的速度 增加 . 9 1.3.2 理解不同的大 O 运行时间 . 10 1.3.3 大 O 表示法指出了最糟情况下 的运行时间 . 12 1.3.4 一些常见的大 O 运行时间 . 12 1.3.5 旅行商 . 13 1.4 小结 . 15 第 2 章 选择排序 . 16 2.1 内
16、存的工作原理 . 16 2.2 数组和链表 . 18 2.2.1 链表 . 19 2.2.2 数组 . 20 2.2.3 术语 . 21 2.2.4 在中间插入 . 22 2.2.5 删除 . 23 2.3 选择排序 . 25 2.4 小结 . 28 第 3 章 递归 . 29 3.1 递归 . 29 3.2 基线条件和递归条件 . 32 3.3 栈 . 33 3.3.1 调用栈 . 34 3.3.2 递归调用栈 . 36 3.4 小结 . 40 第 4 章 快速排序 . 41 4.1 分而治之 . 41 4.2 快速排序 . 47 4.3 再谈大 O 表示法 . 52 4.3.1 比较合并排
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 图解
限制150内