算法之道

作者简介

《算法之道》追求的目标是算法背后的逻辑，是一本启示书，而不是一本包罗万象的算法大全。因此，《算法之道》甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。《算法之道》将算法的讨论分为五大部分：算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。

《算法之道》既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。

书籍目录

前言第一篇  算法基础篇  第1章  从无有到无穷    1.1  意念与现实    1.2  什么是算法    1.3  算法的表示    1.4  算法之魂    1.5  如何比较速度    1.6  算法与计算机的关系    1.7  算法的范畴    1.8  为什么学习算法    思考题  第2章  计数与渐近  ……  第3章  分治与递归第二篇  算法设计篇  第4章  动态规划思想  第5章  贪婪选择思想  第6章  随机化思想第三篇  算法分析篇  第7章  概率分析  第8章  摊销分析  第9章  竞争分析第四篇  经典算法篇  第10章  排序和次序  第11章  搜索与哈希  第12章  最短路径第五篇  难解与无解篇  第13章  可解与不可解  第14章  NP完全问题  第15章  无解与近似结语  算法之道附录  算法随想参考文献

编辑推荐

《算法之道》：揭橥算法之道，求开智慧之门逻辑演绎、生活归纳、趣味交织、入木三分地揭示算法的奥妙。新的角度、新的分析、新的境界、耳目一新地阐述算法的精华。《算法之道》以全新的角度揭示算法的奥秘，内容囊括了所有重要的算法战略和有独特代表性的算法问题。《算法之道》对算法的基本设计与分析战略、高级设计战略、高级分析战略、经典算法问题、难解与近似算法问题进行了深入的讨论。书中选取的每个算法都在某个方面具有独特性，能够彰显算法的精髓。《算法之道》隐含7个悖论和7个奥秘。如果能够发现一二，你将获得奇妙的感受。《算法之道》有如下几个特点：启示：深入探讨算法背后的逻辑，对算法的剖析达到前所未有的境界。独特：同样的算法、相似的问题，选取不同的角度，帮助读者理解到新的高度。简洁：摈弃臃肿繁琐的内容堆砌，精选代表性的算法问题来彰显算法的普遍逻辑。新颖：不同一般的章节组织使条理更为清晰，在内容上引入部分清新的概念和定义。幽默：以讲故事的形式将算法的精华娓娓道来，易于理解和消化。

前言

起初神创造天地。地是空虚混沌，渊面黑暗；神的灵运行在水面上。神说：“要有光”。就有了光。神看光是好的，就把光与暗分开了。神称光为昼，暗为夜。有晚上，有早晨，这是头一日。 ……神就照着自己的形象造人， ……神说：“看哪！我将遍地上一切结种子的菜蔬，和一切树上所结有核的果子，全赐给你们作食物。至于地上的走兽和空中的飞鸟，以及各样爬在地上有生命的物，我将青草赐给它们作食物”。事就这样成了。 神看着一切所造的都甚好。有晚上，有早晨，是第6日。天地万物都造齐了。 图1 米开朗基罗创作的西斯廷教堂穹顶画《创世纪》。这幅画里隐含着算法 6天 圣经上写着：神6天创造天地万有，第7日安歇。 对于神创论者来说，这是不可怀疑的事实。但对于进化论者来说，6天创造一切根本就不可能。 作为一本算法书，我们当然不打算加入到神创论者和进化论者的永无休止的争论当中去。我们关心的是这么一个问题：圣经上为什么给出的是6天，而不是其他的时间长度。不管是神创论者还是进化论者，弄清楚6这个数字的来历很可能会对己方的观点有所帮助。在这6天里，神将他的创作方程式重复了6次，每天1次。对于全能的神来说，他完全可以在1天、1秒或者任何他所愿意的时间长度里创造天地万物，但却为什么是不多不少的6天呢？而不管圣经上的 “1天”是多长，这个问题都是值得讨论的。 我们知道，任何一个自然数的约数中都有1和它本身，而所有小于它本身的因数叫做这个自然数的真约数。例如，6的所有真约数是1、2、3；8的真约数是1、2、4。如果一个数的真约数之和等于这个自然数本身，则这个自然数就称为完全数，或者完美数。例如，6 = 1+2+3，因此6是完美数；而8 ( 1+2+4，因此8不是完美数。因此，神6天创造世界，暗示着该创造是完美的！ 以完美数来昭示创造的完美，似乎合情合理。但问题是，完美数只有6这一个数吗？如果不是，为什么不使用其他的完美数呢？答案是，完美数虽然不止有6这一个，但确实数量稀少。一直到现在（2009年6月），数学家们探索了2600年，并且现代数学家们还借助了超级计算机，但也仅仅找到了47个完美数。其中第1个完美数是6，接下来的4个完美数分别是： 28、496、8128、33 550 336。而第47个完美数有25 956 377个数位，（注意，是数位，不是数值！）它的数值为：243 112 608 × (243 112 609 ? 1)。 完美数的稀少昭示着达到完美的难度，而神选择6天来创造天地万有也许是因为6是最小的完美数，即创造天地万有对于神来说是轻而易举的一件事情…… 完美与算法 完美数由于其各种神秘属性（真约数之和等于自身只是其中的一个性质）而受到了特殊的关注。但到底哪些数是完美数则不是一件容易判断的事情。显然，按照完美数的定义，判断一个数是否是完美数的不二法则是找出它的所有真约数，然后求和看看其是否等于自身。然而这种方法效率太过低下，因为这意味着因式分解，而这是十分困难的（本书后面将会讨论到这个问题）。 如果判断一个数是否是完美数就已经非常困难，那么要找出所有的完美数则更是一个难上加难的任务。因为这就意味着将所有的数进行上面描述的判断验证：因式分解。这似乎是人类不可能完成的任务。即使用世界上超大的计算机来进行计算，情况也不会有任何数量级的改善。 显然，我们需要新的解决方案，而不是发明或使用新的计算工具！研究这样的问题就可以归结到算法的范畴里，因为如何高效地解决问题正是算法要研究的核心课题。 有意思的是，判断和搜索完美数是算法的研究范畴，而算法本身的追求却也是“完美”（见图2）。 图2 算法所追求的理想就是完美 算法无处不在 如果你觉得算法只是用来研究解决找出完美数之类的“漫无边际的问题”，那就大错特错了。 也许算法这个名词听上去很抽象，让人联想不到任何具体的物体。也许你会觉得算法与自己的生活并无太多关系，它只不过存在于那些闲得无聊的数学家或计算机专业人士的脑海中。 但事实真是这样吗？当然不是。如果我们告诉你算法就是解决各种问题的方法，你就不会觉得它太抽象，与生活无关了吧。事实是，算法无处不在。每个人每天都在使用不同的算法来活出自己的人生，比如你去食堂买饭会选择一个较短的队列，而有人则可能选择一个推进速度更快的队列。每天起床后，你可能先读一会儿书，再去吃早饭；另外一个人则可能先去吃早饭，然后读书。所有这些行为都是算法或算法一部分的体现。也许运行这些算法并不在你的思想意识里，也许你并不知道算法在帮助着自己的生活，但它确实是存在的。这些算法也许没有经过精心设计，没有经过仔细分析，但它还是算法！ 2009年7月23日下午，我在游览云南省大理市的蝴蝶泉时由于泉水边的石头很滑，在用泉水洗手时（导游金花说用该泉水洗手会带来好运）不慎滑落到蝴蝶泉水（见图 3）里面，全身湿透。（据说一天至多只会有一个人滑落到泉里，可见本人运气不错！看来“蝴蝶泉边好梳妆”的歌词也许应该改为“蝴蝶泉里好冲凉”。）泉水冰冷透凉，而大理的气温又低。这样，我就面临一个是否更换全身衣服的决定。问题是，旅游团需要马上赶去登游船游览洱海风光，而若找地方或者回旅店换衣服就将赶不上游船。 如何处理这件事情就是一个算法问题：是先上游船再在船上找地方换衣服，还是找个地方换衣服而放弃游览苍山洱海。显然不同的算法有着不同的收益和代价。如果能够在游船上找到合适的地方更换衣服，则采用先上游船再换衣服的算法为佳；否则就是放弃游览的算法更好，因为如果冻病了显然就不划算了。最后，我选择了在游船上更换衣服的算法：在游船上找到了一个贵宾室更衣。 图3 在蝴蝶泉水下洗个手也会涉及算法 算法由问题驱动 算法的发现总是由相关的问题驱动的。拿排序来说，因为生活中到处都充满次序，每个人都要接受自己在某个次序里的位置。比如，各种排名、评优、民意调查等，最后的结果都体现为一个次序！看来，“没有次序无以成方圆”并不是空穴来风！而谈到排序用的方法，人们很自然地想到插入法，因为这种朴素的算法和人的思维方式非常类似：它就是人们打牌时整理手中扑克牌的算法。 但是随着数据量的增大，插入排序的效率缺陷迅速变为人们无法容忍的缺点。于是人们发明了归并排序、堆排序、快速排序等，这些排序的方法大大改善了速度，但是人们却并不满足于此。因此又发明了效率更高的线性排序。表1给出的是各种排序算法平均情况下的效率比较：最上面一行的数字代表输入的规模，如10表示一共有10个数据项，1M表示一共有100万个数据项。其他格子里面的数据为相应算法在相应输入规模下完成排序所需要的时间，单位为毫秒。所有输入数据为随机产生。

章节摘录

插图：到目前为止，我们简要论述了什么是算法、算法之魂、算法和计算机的关系及算法思维，读者应该体会到算法的重要性。但仅仅是因为算法重要就要学习它吗？世界上有很多重要的东西，难道我们都要学吗？即使是计算机专业的学生，不学算法也照样可以编程写软件。那么，我们为什么要学习算法呢？当然，我们有成千个理由要学，但这里仅给出几个。首先，算法是计算机的灵魂。前面已经说过，计算机不能独立于算法而存在，或者说独立于算法的计算机其存在价值要大打折扣。一个程序要完成一个任务，其背后肯定要涉及算法的设计。实际上，程序就是算法的实现，或者说程序是算法的外在体现。学好了算法，就能够设计出更加有效的软件，以最有效的方式完成更为复杂的功能。其次，算法是数学机械化的一部分，能够帮助我们解决复杂的计算问题，其中有的问题就存在于我们的日常生活中。前面讲过，算法无处不在。实际上，人是躲避不了算法的，每天的日常生活都会涉及算法。例如，如何分配自己的时间才能最有效地完成学习或工作任务就会涉及算法。不具备算法知识的人，分配的时候多半会源于自发、非科学的处理方法，难以达到高效。再次，算法作为一种思想，能锻炼我们的思维，使思维变得更清晰、更有逻辑。算法是对事物本质的数学抽象，看似深奥，却体现着点点滴滴的朴素思想。虽然真理未必只有一个，但是只要你掌握了其中的一个，你就掌握了全部，这就像是NP完全问题一样。因此，学会算法的思想，其意义不仅仅在算法本身，对日后的学习生活也会产生深远的影响。

图书封面

---

 算法之道下载 精选章节试读 更多精彩书评

---