基本信息
编辑推荐
CSDN超人气博主、算法专栏达人王晓华力作
淋漓尽致展现算法本质,广泛涵盖常用算法结构及其应用
一本书玩转算法,尽享算法乐趣
内容简介
计算机书籍
本书从一系列有趣的生活实例出发,全面介绍了构造算法的基础方法及其广泛应用,生动地展现了算法的趣味性和实用性。全书分为两个部分,第一部分介绍了算法的概念、常用的算法结构以及实现方法,第二部分介绍了算法在各个领域的应用,如物理实验、计算机图形学、数字音频处理等。其中,既有各种大名鼎鼎的算法,如神经网络、遗传算法、离散傅里叶变换算法及各种插值算法,也有不起眼的排序和概率计算算法。讲解浅显易懂而不失深度和严谨,对程序员有很大的启发意义。书中所有的示例都与生活息息相关,淋漓尽致地展现了算法解决问题的本质,让你爱上算法,乐在其中。
本书适合软件开发人员、编程和算法爱好者以及计算机专业的学生阅读。
算法之大,大到可以囊括宇宙万物的运行规律;算法之小,小到寥寥数行代码即可展现一个神奇的功能。算法的应用和乐趣在生活中无处不在:
历法和二十四节气计算使用的是霍纳法则和求解一元高次方程的牛顿迭代法;
音频播放器跳动的实时频谱背后是离散傅立叶变换算法;
DOS时代著名的PCX图像文件格式使用的是简单有效的RLE压缩算法;
RSA加密算法的光环之下是朴实的欧几里德算法、蒙哥马利算法和米勒-拉宾算法;
井字棋、黑白棋、五子棋和俄罗斯方块游戏背后是各种有趣的AI算法;
华容道游戏求解的简单穷举算法中还蕴藏着对棋盘状态的哈希算法;
遗传算法神秘不可测,但用遗传算法求解0-1背包问题只用了60多行代码……
作译者
2005年毕业于华中科技大学,目前在中兴通讯上海研发中心从事光纤接入网通讯设备开发,担任EPON(以太网无源光网络)业务软件开发经理,参与开发的PON设备在全球部署过亿线,为数亿家庭提供宽带接入服务。
业余时间喜欢研究算法和写作博客(http://blog.csdn.net/orbit),最大的乐趣就是用程序解决生活中的问题:
为了方便使用Visual Studio 6.0开发软件,曾特意编写并开源了一个tabbar插件;
为了文档安全,开发了一个基于layerFSD技术的透明文件加密系统;
使用Source Insight软件觉得不习惯,于是以外挂的形式开发了TabSiPlus插件……
算法可以做的事情还有很多,期待我们会有更多发现!
目录
1.1 什么是算法 2
1.2 程序员必须要会算法吗 2
1.2.1 一个队列引发的惨案 3
1.2.2 我的第一个算法 5
1.3 算法的乐趣在哪里 7
1.4 算法与代码 8
1.5 总结 9
1.6 参考资料 9
第2章 算法设计的基础 10
2.1 程序的基本结构 10
2.1.1 顺序执行 10
2.1.2 循环结构 11
2.1.3 分支和跳转结构 13
2.2 算法实现与数据结构 16
2.2.1 基本数据结构在算法设计中的应用 16
2.2.2 复杂数据结构在算法设计中的应用 19
2.3 数据结构和数学模型与算法的关系 24
2.4 总结 25
2.5 参考资料 25
前言
程序员对算法通常怀有复杂的感情,算法很重要是大家的共识,但是是否每个程序员都必须学算法是主要的分歧点。本书是想重新定义程序员对算法的理解,并不想通过说教的方式给出到底是学还是不学的结论。很多人可能觉得像人工智能、视频与音频处理以及数据搜索与挖掘这样高大上的内容才能称为算法,往往觉得算法深不可测。但是这些其实都不是具体的算法,而是一系列算法的集合,这里面既有各种大名鼎鼎的算法,比如神经网络、遗传算法、离散傅里叶变换算法以及各种插值算法,也有不起眼的排序和概率计算的算法。你必须深入地了解它们,才会领略到算法的实质——解决问题。忽视这一点,片面地或抽象地理解算法,就会使对算法的理解变得形而上学。在我的博客里就有人留言质疑:“穷举也算是算法?”且不说搜索和枚举是算法的基础设计模式之一,单就那么多的NPC问题(比如著名的汉密尔顿回路问题,至今还没有找到多项式时间的算法),实际上,从只有穷举算法和其他随机搜索算法才能求解这一点看,任何人都不能小看它。
狭隘的算法定义会将自己局限在一个小角落里,从而错过了整个色彩缤纷的算法世界。本书将带你开启一段算法之旅,在这里,你将会看到各种构造算法的基础方法,比如贪婪法、分治法、动态规划法,等等,也可以通过一个个示例看到如何应用这些算法来解决实际问题。通过对“爱因斯坦的思考题”“三个水桶等分水”“妖怪与和尚过河问题”等趣味智力题的计算机求解算法设计,你可以领会到算法设计的三个关键问题,以及对这些问题的处理方法,为以后解决这样的问题提供举一反三的基础。
在生活中,凡是有乐趣的地方就有算法。本书将介绍生活中无处不在的算法。在历法计算的章节里,你会看到霍纳法则(Horner’s rule)的使用和求解一元高次方程的牛顿迭代法;音频播放器上跳动的频谱,背后是离散傅里叶变换算法;DOS时代著名的PCX图像文件格式使用的RLE压缩算法是如此简单,但是却非常有效;RSA加密算法的光环之下是朴实的欧几里得算法、蒙哥马利算法和米勒·拉宾算法;华容道游戏求解的简单穷举算法中还蕴藏着对棋盘状态的哈希算法……遗传算法神秘不可测,但是用遗传算法求解0-1背包问题只用了60多行代码。事实上,抛开对遗传算法的深层次研究和在各种专业领域内的扩展应用,单就算法原理来说,它就是这么简单。深蓝战胜卡斯特罗之后,人类棋手在与计算机的博弈中就完全处于下风,人工智能真的这么神奇?人工智能确实是个神奇的领域,但就计算机下棋这件事来说,却并不怎么神奇,算法的基本原理简单得让人难以置信,看看第23章你就知道了。
算法之大,大到可以囊括宇宙万物的运行规律,算法之小,小到寥寥数行代码即可展现一个神奇的功能。算法是琐碎的,以至于常常被人们忽视,然而忽视算法能力的培养所带来的代价是巨大的,第1章介绍的环形队列的例子就是一个最好的说明。我面试过很多求职者,我常常会让他们手写一个算法,我的题目是这样的:有一个由若干正整数组成的数列,数列中的每个数都不超过32,已知数列中存在重复的数字,请给出一个算法找出这个数列中所有重复出现的数。我期望求职者给我一个正确的算法实现,接下来我会问这个算法的时间复杂度是什么,有没有考虑过存在一个O(n)时间复杂度的算法。大部分求职者都知道自己的算法是O(n2)时间复杂度,但是都否认存在O(n)时间复杂度的算法。事实上这个题目是可以有O(n)时间复杂度的算法的,因为大家都忽略了一个重要的条件。这个题目并不难,但是仍有将近三分之一的面试者无法给出正确的算法,有的甚至还给我一张白纸。有人犯错误是正常现象,但是让我意外的是居然有三分之一的人写不出这个算法,算法设计的基本功被无视到这种地步是不正常的。
程序员谈到算法言必称一些高大上的词汇,但是这些专有名词大部分人是用不到的,以至于人们常常认为算法不过如此,不会又如何?这种思想变得极端就会让人忽视算法的基础设计能力,这才是最要命的。在我们维护的网络设备上,用户的数据关系错综复杂,一个对线性表进行二重循环都想不到的人又怎么可能会维护这些数据?我希望程序员们提高基础的算法能力,先从培养兴趣开始或许是一个不错的切入点。
本书挑选的算法例子,都围绕着“趣”字展开,都是简单且在生活中常见的算法,可能有些是你还没有意识到的。我上学的时候曾经做过一个MP3播放器程序,你可能觉得这主要就是利用一些音频解码算法吧?是的,这个是主要部分,但是一个功能完整的播放程序还用了很多你想不到的算法:为增加频谱显示和均衡器功能,使用了离散傅里叶变换算法;为计算频率功率谱,使用了加权平均值算法;为了匹配硬件输出设备与解码算法的性能差异,需要一个有多个缓冲区的队列管理音频数据块,这就引入了滑动窗口算法;为提供按照专辑名称或作者名称排序功能,使用了快速排序算法;为了平滑均衡器调节对音频的影响,使用了三次样条曲线插值算法;为了在两首歌曲之间切换时压制刺耳的杂音(通过填充一些舒适噪声的方式实现),还使用了正弦信号发生器算法。这些你都没有想到吧?其实还有更多的例子,比如大型项目管理软件中的工作节点排序功能和关键路径功能,背后支撑它们的却是简单的有向图拓扑排序算法。这是不是很有趣?生活中处处都是算法,程序员又怎么可能与算法绝缘?
再次重申一点,本书没有任何关于算法重要性的说教,当你看到本书时,我希望你的表情是“啊哈,原来如此!”,或者是“嗯,有意思!”,并从中获得乐趣。本书几乎所有章节都有相关算法实现和功能演示的代码,读者可以到我的博客(http://blog.csdn.net/orbit/)中下载,也可以到图灵社区本书主页(www.iTuring.cn/book/1604)下载使用。
序言
读《算法的乐趣》的乐趣超出了我的预料。
说到算法,大部分计算机专业的同学的第一反应估计是MIT出版社的经典教材《算法导论》(Introduction to Algorithms)。这是一本由浅入深的好书,堪称“神书”——别看书挺厚,但是对初学者来说很难弄懂的问题也娓娓道来,让人看一遍就明白;而且作者用最简单的英语词汇和句法写书,以至于世界各地的学生们,不需要英语很好,即可读懂原版。只是看完这本大部头之后,总有一些意犹未尽的感觉——对我们日常生活中常见的比如音乐播放器里以及电子游戏里的算法并没有太多介绍。而这些正是《算法的乐趣》中主要的部分。
在Amazon上,另外两本排名靠前的经典算法教材是Jon Kleinberg的《算法设计》(Algorithm Design)和Steven S. Skiena的《算法设计手册》(The Algorithm Design Manual)。这两本出自名家之手的教材和很多教材一样,按照算法的类型或者背后的设计思路来组织内容。这是教材应该做的,“授人以鱼不如授人以渔”,传授思路而不是算法本身是教材的写作目的。可是算法最有意思的地方首先在于算法本身,因为算法是为了解决实际问题而设计的,所以让大家认识到算法奥妙的自然顺序应该是先展示有趣的问题,再展示优雅的算法,最后归纳设计思路。而这正是《算法的乐趣》吸引人的地方。
说到乐趣,总让我想起我学习和使用数学知识的经历。虽然我的学位是关于统计机器学习的,而且毕业后一直从事相关工作,但是我从小学一年级到博士第三年都对数学毫无兴趣,因为学校的老师和数学成绩好的同学都说不明白数学的用处,以至于我一直以为数学的作用只是锻炼和展示自己的聪明,博得老师的表扬,成为陈景润那样为国争光的英雄。而这些对我实在没有吸引力,而且我认为恐怕对绝大部分学生都没什么吸引力。
我认识到数学的价值,是因为在博士第三年把研究方向换到了统计机器学习。在读教材的时候,我曾想验证“数学无用”,所以费尽心力地试图写一个程序来判断一个64×64像素的图片里到底是数字“1”还是数字“9”,却发现无论如何也很难写一个有效的程序;可是利用教材里的数学知识却能设计和“训练”一个数学模型,准确地识别任意字符。因为体会到了数学的用处,我兴奋地用了一年的时间复习大学本科的数学课程,然后才读懂了人工智能的专业教材和论文。此后才有所创新,发表论文,到博士毕业。这整个过程用了三年,而效果超过了之前19年数学教育的效果。
在这个过程中,我自然而然地开始注意数学知识的前因(比如为什么人们会关注长度、面积,怎么会有人考虑勾股定理这样的规律)以及后果(今天的数学知识能给物理学和机器智能带来什么样的帮助),也开始归纳和了解各种数学系统背后的规律,能体会哥德尔定理阐述的意思。当然,也破除了“数学是各种科学之母”之类的迷信,数学当然不是“科学之母”,而是“科学之子”,是先有物理学、力学和天文学,才有的数学;先有应用场景后有工具,先有探索后有归纳。
算法也是如此。先有工程问题需要解决,算法是解法,设计算法是寻求解法。虽然算法作为一门科学是归纳寻求解法的思路,但学习这种归纳法的前提是能体会各种具体算法的用处和效果。意识到这一点,自然也就破除了诸如“学好数学才能学好算法”之类的迷信。而把算法解决的各种有趣问题罗列出来,把算法的可爱之处展示给愿意发现和体会生活中点滴乐趣的读者们,正是《算法的乐趣》在技术价值之外的一层社会价值。
十年前,当我们坐在课堂里学习算法的时候,我们学到的是如何用人脑寻求解法,然后把解法写成程序,让计算机照着执行去解决问题。这是“经典算法”。最近十几年,随着Internet产业的兴起,Internet服务在不断取代原来由人提供的服务,这就要求机器拥有一定程度上能取代人的“智能”。在搜索引擎、推荐系统和广告系统等各个领域里,类似上述“识别数字”的问题越来越多,而人工智能和机器学习的应用也越来越深入我们的生活。机器学习算法的设计目标和“经典算法”不同——不是让人来想解法,而是让计算机从数据归纳知识——有了这些知识,计算机就能自己寻求解法。
虽然经典算法和机器学习算法之间的差别大得如同一场革命,但是由经典而入机器学习的过程却是自然而然的。比如《算法的乐趣》中介绍的曲线拟合问题,就是supervised learning(有监督学习),而音乐播放器里常用的傅里叶变换和其他时域频域变换则是unsupervised learning(无监督学习)的技术基础,棋类游戏算法是博弈论和reinforcement learning(强化学习)的经典例子。我常见有朋友从读数学教材开始探索机器学习和人工智能算法,也常看到有人不堪忍受长时间缺乏乐趣的探索以至于半途而废。如果是这样,也许不如从《算法的乐趣》开始这个探索过程。
我曾经以为从乐趣出发阐述算法的书会从西方发芽,没想到先看到了一本中文书。这真超出了我的预料。
王益
LinkedIn高级主任分析师
序二
当图灵出版社的编辑找到我希望我为这本书写个序的时候,我和旁边的同事调侃了一句:又一本简版的《算法导论》要诞生了。但是我还是下载了附件阅读了这本书,当翻到目录的时候,我的兴趣就被燃起来了,转头和同事说,也许这是一本不错的书。
程序员到底需不需要学习算法?这个问题被争论的次数绝对不亚于“Java是不是最好的语言”“VIM和Emacs谁是最好的编辑器”“程序员是不是需要学习数学”。为了避免陷入这样的争论里,我们先对“算法”一词做个转换定义,什么是算法?下面我举几个我亲身经历的例子。
有一次我们发布了一个APP,在注册时要求用户输入自己的真实姓名,但是粗心的工程师忘记了要求用户填写自己的性别,更可怜的是在欢迎页上面明晃晃地写着“欢迎XXX先生注册XX网”,可是应用已经发布到了App Store,到底怎么办?有一位工程师提出了一个办法,我们根据已有的用户姓名和性别作为训练集,来预测新用户到底是男还是女,为了让这个错误尽快得到修复,我们使用了最简单的朴素贝叶斯分类算法,最终测试集上的预测准确率达到93%,也就是说我们解决了93%用户的体验问题。我把这类算法称为专业类算法,也就是招聘网站上算法工程师要求的算法,例如图像处理工程师、数据挖掘工程师等。
媒体评论
……
“我曾经以为从乐趣出发阐述算法的书会从西方发芽,没想到先看到了一本中文书。这真超出了我的预料。”
——王益,LinkedIn高级主任分析师
“这本书给我最大的惊喜是没有像一般的算法书一样单纯地去讲算法和数据结构本身,那样无论语言多风趣,只要一谈到关键的问题也会马上变得无趣起来。作者在每一章都举给出了一个实际的问题,然后尝试用算法去解决这个问题,没有局限于通用类算法,而是同时涵盖逻辑类算法、通用类算法和专业类算法,真正是在训练读者解决问题的能力,而解决问题的能力,正是任何一家公司所需人才的最核心的技能。”
——黄鑫((飞林沙)),极光推送首席科学家
“如果说《啊哈!算法》是算法界的小白书,内容太少看得不过瘾,那么这本《算法的乐趣》或许可以带你一起牛逼一起飞。当我刚拿到书的目录的时候,我就很期待,因为终于有一本算法书可以系统地和大伙说一说这些我也很想与大伙说的伟大算法。”
——啊哈磊,《啊哈!算法》作者
作者其它作品
MapReduce 2.0源码分析与编程实战
- ¥49.00
- ¥37.73
- 数字逻辑与数字电子技术