[算法之道(第2版)].邹恒明.扫描版

算法经典书籍，适合各个阶段的开发者查阅。斗★★斗,女求于至简,归于永恒n Pursuit of Absolute Simplicity谨以此书献给夫人蕾蕾,女儿雨洁、雨蓉、雨恒、兩宜。To my wife Lily and daughter Charissa, Elizabeth, Grace. Ida,●2e:::前言前盲V对于神创论者来说,这是不可怀疑的事实。但对于进化论者来说,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、33550336.而第47个完美数有25956377个数位(注意,是数位,不是数值),它的数值为:24312608×(24312609-1)完美数的稀少昭示着达到完美的难度,而神选择6天来创造天地万有也许是因为6是最小的完美数,即创造天地万有对于神来说是轻而易举的一件事情…1完美与算法:完美敷由于其各种神秘属性(真约数之和等于自身只是其中的一种性质)而受到了特殊的关注。但到底哪些数是完美数则不是一件容易判断的事情。显然,按照完美数的定义,判断一个数是否是完美数的不二法则是找出它的所有真约数,然后求和看看其是否等于自身。而这种方法效率太过低下,因为这意味着因式分解,而这是十分困难的〔本书后面将会讨论到这个问題)如果判断一个数是否是完美数就已经非常困难,那么要找出所有的完美数则更是一个难上加难的任务。因为这就意味着将所有的数进行上面描述的判断验证:因式分解。这似乎是人类不可能完成的任务。即使用世界上超快的计算机来进行计算,情况也不会有任何数量级的改善。显然,我们需要新的解决方案,而不是发明或使用新的计算工具!研究这样的解决方案就可以归结到算法的范畴里,因为如何高效地解决问题正是算法要研究的核心课题。有意思的是,判断和搜索完美数是算法的研究范畴,而算法本身的追求却也是“完美”见图2)时间精确)(完美】(空间效率图2算法所追求的理想就是“完美”+m+算法无处不在如果你觉得算法只是用来研究解决找出完美数之类的“漫无边际的问题”,那就大错特错了。也许算法这个名词听上去很抽象,让人联想不到任何具体的物体。也许你会觉得算法与自己的生活并无太多关系,它只不过存在于那些闲得无聊的数学家或计算机专业人士的脑海中。但事实真是这样吗?当然不是。如果我们告诉你算法就是解决各种问题的方法,你就不会觉得它太抽象,与生活无关了吧。事实是,算法无处不在,每个人每天都在使用不同的算法来活出自己的人生,比如你去食堂买饭会选择一个较短的队列,而有人则可能选择一个推进速度更快的队列。每天起床后,你可能先读一会儿书,再去吃早饭;另外一个人则可能先去吃早饭,然后再看书。所有这些行为都是算法或算法一部分的体现。也许运行这些算法并不在你的思想意识里,也许你并不知道算法在帮助自己的生活,但它确实存在。这些算法也许没有经过精心设计,没有经过仔细分析,但它还是算法!2009年7月23日下午,我在游览云南省大理市的蝴蝶泉时由于泉水边的石头很滑,在用泉水洗手时〔导游金花说用该泉水洗手会带来好运)不慎滑落到蝴蝶泉水(见图3)里面全身江透。(据说一天至多只会有一个人滑落到泉里,可见我的运气不错!看来“蝴蝶泉边妤梳妆”的歌词也许应该改为“蝴蝶泉里妤冲凉η。)泉水冰冷透凉,而大理的气温又低。这样,我就面临一个是否更换仝身衣服的选择。问题是,旅游团需要马上赶去登游船游览洱海风光,而若找地方或者回旅店换衣服就将赶不上游船。如何处理这件事慵就是一个算法问題:是先上游船再在船上找地方换衣服,还是找个地方换衣服而放弃游览苍山洱海。显然不同的算法有着不同的收益和代价。如果能够在游船上找到合适的地方更换衣服,则采用先上游船再换衣服的算法为佳;否则就是放弃游览的算法更好,因为如果冻病了显然就不划算了。最后,我选择了在游船上更换衣服的算法:在游船上找到了一个贵宾室更衣前言Ⅶ图3在蝴蝶泉水下洗个手也会涉及算法算法由问题驱动算法的发现总是由相关的问题驱动的。拿排序来说,因为生活中到处都充满次序,每个人都要接受自己在某个次序里的位置。比如,各种排名、评优、民意调查等,最后的结果都体现为一个次序!看来,“没有次序无以成方圆”并不是空穴来风!而谈到排序用的方法人们很自然地想到了插入法。因为这种朴素的算法和人的思维方式非常类似:它就是人们打牌时整理手中扑克牌的算法但是随着数据量的增多,插入排序的效率缺陷迅速变为人们无法容忍的缺点。于是人们发明了归并排序、堆排序、快速排序等,这些排序的方法大大改善了速度,但是人们却并不满足于此,因此又发明了效率更高的线性排序。表1给出的是各种排序算法平均情况下的效率比较:最上面一行的数字代表输入的规模,如10表示一共有10个数据项,1M表示一共有100万个数据项。其他格子里面的数据为相应算法在相应输入规模下完成排序所霄要的时间,单位为毫秒。所有输入数据为随机产生表1部分排序算法的时间效率比较〔单位;毫秒排序算法10100lk10k100kIM冒泡排序0.00027600056430.545618l74549432选择排序0.00023700064380.488474717478694插入排序000212206190764565145515621希尔排序/增量3000052200033720.03605184.15261堆排序00004500029900405316506I前言(续排序算法10100lk100kIM归并排序0.0007230.0062250066056l5.48快速排序0.000291000305100300313.63439基数排序/进制100000518100210L651.6511428117基数排序进制100000161340.0260.13912648.39489注;1.算法迳行环境为 Intel酷睿2双核E840,3.0 GHz, Windows7x642.本表敷据由作者所授“数据蚰构”謀的胡嘉斌同学测诚所得一个个新的算法都是为了解决前面算法遣留的问题而产生的。从表1里的数字可以看出,一般来说,随着新的算法出现,排序效率在不断提高。不过,虽然每个算法似乎解决了前面算法的遗留问题,但新的问题也会被有意或无意地引入。例如,线性排序虽然将排序的时间复杂性降低到线性级,但各种前提条件极大地限制了其应用范围。也许这就是算法永远也不能或不会停止发展的一个原因吧。算法是计算机的灵魂因为人不是全能的,一个时刻只能做一件事情,所以做事情就要有一个步骤。由于算法要满足人的这种特性,因此它通常表示为一个做事情的行为序列。因此,从一般意义上说,算法就是求解问题的步骤,由于计算机的计算操作完全是一步一步进行,因此算法的上述性质用于计算机是再合适不过了,可以说算法弥漫在计算机的一切行为上,如果说操作系统是计算机的心智,那么算法就是计算机的灵魂。理解灵魂当然不是一件容易的事情,由于它高废抽象与简洁,许多学生都望而却步。先看一个纸牌魔术(见图4)1〕任选一位观众将一副扑克牌充分洗好。之)背对观众,请观众随杋抽出一张牌,记住牌面,然后将这张牌放回整副牌的最上面。3)接过牌后,洗牌几次。洗牌的时候保持最上面一张牌不动4)对观众说:“我来教你麑法,只要吹一口气,就能把刚才你抽的牌吹到任意位置上”5)请观众说出一个数字,比如说10,然后一边吹气,一边想着刚才说的数字106)在吹完气后,请观众一张一张地将上面的牌取出放在桌上。7)到第10张时,将牌翻开,发现并不是其原来抽的牌。8〕接回整副牌,并把上一个步骤里取出堆放在桌上的牌收起,仍放在整副牌的最上面。9)然后洗牌几次,洗牌的时候保持上面放回来的那堆牌不动10)从观众手上拿回刚才翻开的那张牌,插入最上面9个位置中的任意一个11)对观众说:“你刚才不是在想着那个数字的时候吹的气,而是在吹气的时候想着那前言Ⅸ个数宇,而这是完全不同的两回事。我现在演示如何吹气.”对着牌吹一口气。12)请观众从上到下数牌,到第10张时翻开,3)这张翻开的牌就是观众一开始抽的那张牌读者看明白了上面的这个魔术了吗?这里面隐藏着一个算法。如果看懂了就可以在朋友面前一显身手了。当然,如果没有看懂也没有什么关系。算法本来就不是轻易让人看懂的嘛432A654图4算法无处不在,就连扑克魔术都有其背后支持的算法对于一些吹毛求疵的人来说,也许会說这个纸牌魔术不是算法。至少这与我们研究算法的人打交道的常见算法不太一样。这没有什么关系,来看下面的一段伪代码:PARTITION (A, P, q)//A是一个实数数组,p、q是该数组的上下限x=A[p]i//A[p]被选中E。〓(j=p+1:j<=:j++)±E(A[力]<=x){i=i+1;temp =A[ili//以下三行交换A[1]和A[]的内容A[1]=A[j];A[ 3]=temp;temp =A[i]//以下三行交换A[i]和A[p]的内容A[i]=A[P];A Ip]=temp;tun主;读者能看出来这个伪代码程序片段完成的是什么功能吗?要分祈一个算法,似乎就更难了。读者能看出下面的C程序片段里面“ laugh+”语句执行了多少次吗?E。x(i=1:i<=n;主*=2)E。z(=1:ji;j+)laugh++i如果这些问题读者都能回答,那么恭喜你。看来算法分析对于读者来說将是件很容易的事情,不过可能也不一定。如果你回答不出这些问题,不用担心,因为回答诸如此类的问题就是本书的目的。当然了,本书回答的远不止这么几个简单问题,而是会阐述更重要的算法精髓:算法思想、战略和分析!本书内容安排本书追求的目标是算法背后的逻辑。因此,它不可能是一本包罗万象的算法大全,而是一本启示书。因此,本书甄选了那些最能够展现算法思想、战略和精华,并能够有效训练算法思维的内容。本书的选材遵循的规则是:书中选取的每个算法都在某个方面具有独特性,能够彰显算法的精髓本书将算法的讨论分为五篇:算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每篇分别讨论算法的一大方面;基础、设计、分析、经典和难解问题。如图5所示箅法之道算法基础篇算法设计篇算法分析萬]「经典算法篇][难解与无解篇]「结言「从[计「分动责「随「概「摊竞排|「规「最「易N「无语无数治态婪机[率销争序索短解P解有与与规选化分分与与路与完与到断递划择思析析析次散径|全近无近归思思|想序|列问似穷想想题图5本书内容框架本书第一篇是算法基础篇,讨论基本的算法设计思想与算法分析方法和手段,包括第1-3章。第1章讨论从无有到无穷、什么是算法、算法的表示、算法之魂、算法与计算机的关系、算法的范畴和为什么学习算法。第2章讨论算法的正确性、时空效率和时空特性分析、计数分析方法、算法设计、渐近丧示与分析。第3章阐述算法设计的最基本战略:分治与递归。具体内容包括分而治之为上策、分治策略中的递归、求解递归表达式、乘法及乘方迳算、矩阵乘法、斐波那契数的计算、LSI布线和多项式乘法第二篇为算法设计篇,讨论算法中常见且重要的战略或思想,包括第4~6章。第4章讨论什么是动态规划,流水线问题、最长公共子序列问题、最优二叉搜索树问题、记忆递归