算法之道 完整版

★ 求于至蒿,归于永恒 n Pursuit of Absolute Simplicity 谨以此书献给夫人蕾蕾,女儿雨洁、雨蓉、雨恒、雨宜 To my wife Lily and daughter Charissa, Elizabeth, Grace, Ida. 对于神创论者来说,这是不可怀疑的事实。但对于进化论者来说,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、49%6、8128、33550336.而第47个完美数有25956377个数位(注意, 是数位,不是数值),它的数值为:24312608×(2412609-1) 完美数的稀少昭示着达到完美的难度,而神选择6天来创造天地万有也许是因为6是最 小的完美数,即创造天地万有对于神来说是轻而易举的一件事情... :完美与算法 完美数由于其各种神秘属性(真约数之和等于自身只是其中的一种性质)而受到了特殊 的关注。但到底哪些数是完美数则不是一件容易判断的事情。显然,按照完美数的定义,判 断一个数是否是完美数的不二法则是找出它的所有真约数,然后求和看看其是否等于自身。 而这种方法效率太过低下,因为这意味着因式分解,而这是十分困难的(本书后面将会讨论 到这个问题) 如果判断一个数是否是完美数就已经非常困难,那么要找出所有的完美数则更是一个难上加 难的任务。因为这就意味着将所有的数进行上面描述的判断验证:因式分解。这似乎是人类不可 能完成的任务。即使用世界上超快的计算机来进行计算,情况也不会有任何数量级的改善 显然,我们需要新的解决方案,而不是发明或使用新的计算工具!研究这样的解决方案 就可以归结到算法的范畴里,因为如何高效地解决问题正是算法要研究的核心课题。 有意思的是,判断和搜索完美数是算法的研究范畴,而算法本身的追求却也是“完美 (见图2) VI 时间 精确)(完美】《空间 效率 图2算法所追求的理想就是“完美” 算法无处不在 如果你觉得算法只是用来研究解决找出完美数之类的“漫无边际的问题”,那就大错特 错了。 也许算法这个名词听上去很抽象,让人联想不到任何具体的物体。也许你会觉得算法与自 己的生活并无太多关系,它只不过存在于那些闲得无聊的数学家或计算机专业人士的脑海中 但事实真是这样吗?当然不是。如果我们告诉你算法就是解决各种问题的方法,你就不 会觉得它太抽象,与生活无关了吧。事实是,算法无处不在。每个人每天都在使用不同的算 法来活出自己的人生,比如你去食堂买饭会选择一个较短的队列,而有人则可能选择一个推 进速度更快的队列。每天起床后,你可能先读一会儿书,再去吃早饭;另外一个人则可能先 去吃早饭,然后再看书。所有这些行为都是算法或算法一部分的体现。也许运行这些算法并 不在你的思想意识里,也许你并不知道算法在帮助自己的生活,但它确实存在。这些算法也 许没有经过精心设计,没有经过仔细分析,但它还是算法! 209年η月23日下午,我在游览云南省大理市的蝴蝶泉时由于泉水边的石头很滑,在 用泉水洗手时(导游金花说用该泉水洗手会带来妤运)不慎滑落到蝴蝶泉水(见图3)里面 全身湿透。〔据说一天至多只会有一个人滑落到泉里,可见我的运气不错!看来“蝴蝶泉边 好梳妆′′的歌词也许应该改为“蝴蝶泉里妤冲凉”)泉水冰冷透凉,而大理的气温又低。这 样,我就面临一个是否更换全身衣服的选择。问题是,旅游因需要马上赶去登游船游览洱海 风光,而若找地方或者回旅店换衣服就将赶不上游船 如何处理这件事情就是一个算法问题:是先上游船再在船上找地方换衣服,还是找个地 方换衣服而放弃游览苍山洱海。显然不同的算法有着不同的收益和代价。如果能够在游船上 找到合适的地方更换衣服,则采用先上游船再换衣服的算法为佳;否则就是放弃游览的算法 更好,因为如果冻病了显然就不划算了。最后,我选择了在游船上更换衣服的算法:在游船 上找到了一个贵宾室更衣。 前言VII 图3在蝴蝶泉水下洗个手也会涉及算法 算法由问题驱动 算法的发现总是由相关的问题驱动的。拿排序来说,因为生活中到处都充满次序,每个 人都要接受自己在某个次序里的位置。比如,各种排名、评优,民意调查等,最后的结果都 体现为一个次序!看来,“没有次序无以成方圆”并不是空穴来风!而谈到排序用的方法, 人们很自然地想到了插入法。因为这种朴素的算法和人的思维方式非常类似:它就是人们打 牌时整理手中扑克牌的算法。 但是随着数据量的增多,插入排序的效率缺陷迅速变为人们无法容忍的缺点。于是人们 发明了归并排序、堆排序、快速排序等,这些排序的方法大大改善了速度,但是人们却并不 满足于此,因此又发明了效率更高的线性排序。表1给出的是各种排序算法平均情况下的效 率比较:最上面一行的数字代表输入的规模,如10表示一共有10个数据项,1M表示一共 有100万个数据项。其他格子里面的数据为相应算法在相应输入规模下完成排序所需要的时 间,单位为毫秒。所有输入数据为随机产生 表1部分排序算法的时间效率比较 单位:毫秒) 排序算法 10 100 lk 10k 100k IM 冒泡排序 0.000276 0.005643 0545 61 8174 549432 选择排序 0000237 0.006438 0.488 47 4717 478694 插入排序 0.000258 0.008619 0.7 56 5145 515621 希尔排序/增量3 0.000522 0003372 0036 0.518 4.152 61 堆排序 0.00045 0002991 0.04l 0.531 6506 前 (续) 排序算法 10 100 lk IOk 100k 归并排序 0.000723 0.006225 0.066 0.561 5.48 70 快速排序 0.000291 0003051 0.030 031I 3.634 39 基数排序/进制100 0.005181 0.021 0.165 1.65 11428 117 基数排序进制1000 0016134 0.026 0.139 1264 8.394 注;1.算法适行环境为 Intel酷睿2双核E8400,3.0GHz, windows7x64 2.本表数据由作者所授“数据蛄构”课的胡嘉斌同学测试所得 个个新的算法都是为了解决前面算法遗留的问题而产生的。从表1里的数字可以看 出,一般来说,随着新的算法出现,排序效率在不断提高。不过,虽然每个算法似乎解决了 前面算法的遺留问题,但新的问题也会被有意或无意地引入。例如,线性排序虽然将排序的 时间复杂性降低到线性级,但各种前提条件极大地限制了其应用范围。也许这就是算法永远 也不能或不会停止发展的一个原因吧 算法是计算机的灵魂 因为人不是全能的,一个时刻只能做一件事情,所以做事情就要有一个步骤。由于算法 要满足人的这种特性,因此它通常表示为一个做事情的行为序列。因此,从一般意义上说, 算法就是求解问题的步驟。由于计算机的计算操作完全是一步一步进行,因此算法的上迷性 质用于计算机是再合适不过了,可以说算法弥漫在计算机的一切行为上。如果说操作系统是 计算机的心智,那么算法就是计算机的灵魂 理解灵魂当然不是一件容易的事情,由于它高度抽象与简洁,许多学生都望而却步。先 看一个纸牌魔术(见图4) 1)任选一位观众将一副扑克牌充分洗好。 2)背对观众,请观众随杋抽出一张牌,记住牌面,然后将这张牌放回整副牌的最上面 3)接过牌后,洗牌几次。洗牌的时候保持最上面一张牌不动 4)对观众说:“我来教你魔法,只要吹一口气,就能把刚才你抽的牌吹到任意位 置上 5)请观众说出一个数字,比如说10,然后一边吹气,一边想着刚才说的数字10 6)在吹完气后,请观众一张一张地将上面的牌取出放在桌上。 7)到第10张时,将牌翻开,发现并不是其原来抽的牌 8〕接回整副牌,并把上一个步骤里取出堆放在桌上的牌收起,仍放在整副牌的最上面 9)然后洗牌几次,洗牌的时候保持上面放回来的那堆牌不动。 10)从观众手上拿回刚才翻开的那张牌,插入最上面9个位置中的任意一个 11)对观众说:“你刚才不是在想着那个数字的时候吹的气,而是在吹气的时候想着那 前言IX 个数宇,而这是完全不同的两回事。我现在演示如何吹气”对着牌吹一口气 12)请观众从上到下数牌,到第10张时翻开, 13)这张翻开的牌就是观众一开始抽的那张牌 读者看明白了上面的这个魔术了吗?这里面隐藏着一个算法。如果看懂了就可以在朋友 面前一显身手了。当然,如果没有看懂也没有什么关系。算法本来就不是轻易让人看懂的嘛 : 图4算法无处不在,就连扑克魔术都有其背后支持的算法 对于一些吹毛求疵的人来说,也许会說这个纸牌魔术不是算法。至少这与我们研究算法 的人打交道的常见算法不太一样。这没有什么关系,来看下面的一段伪代码 PARTITION (A, P, q) //A是一个实数数组,p、q是该数组的上下限 x=A[P]; //AIp]被选中 f。E(j=p+1;j