《程序设计经典名著--算法之美中文译文.doc》由会员分享，可在线阅读，更多相关《程序设计经典名著--算法之美中文译文.doc（10页珍藏版）》请在金锄头文库上搜索。
1、第0章序言环顾四周。计算机和网络无处不在，它为复杂的人类活动纺织了一张巨大的网：教育，商业，娱乐，研究，制造业，卫生管理，人类通讯甚至战争。支撑起这种惊人增长的是两个主要的科技：高速发展的微电子技术和芯片设计已经带给我们越来越快的计算机硬件。这本书讲述的是另一个知识产业的故事：计算机革命的动力：高效算法。这是令人着迷的故事。请搬好凳子慢慢听我讲来！0.1 书籍和运算法则有两个想法改变了世界。1448年德国美因兹，一个名叫Johann Gutenberg的金匠发现了把活动金属块这在一起来印刷书籍的方法。随着知识不断传播，黑暗时代从此结束，人类思想被完全解放，科学和技术迎来光明，工业革命爆发。很多
2、历史学家把这归功于活版印刷术，设想一下只有极少数人能够阅读知识这个世界会是什么样子！但还有一部分人这一切的关键不是活版印刷术而是运算法则。今天我们已经习惯于使用阿拉伯数字来书写数字，象Gutenberg那样把1448写成MCDXLVIII是非常容易被忘记的（译者注：MCDXLVIII是罗马数字，它代表1448，罗马数字是欧洲在阿拉伯数字（印度数字）传入之前使用的一种数码，现在应用较少。它的产生晚于中国甲骨文中的数码，更晚于埃及人的十进位数字。但是，它的产生标志着一种古代文明的进步）。你怎么样去对两个罗马数字进行相加呢？什么是MCDXLVIII + DCCCXII呢？（再想想如何对它们相乘。）甚
3、至象Gutenberg这样聪明的人大概也只会使用手指头对两个很小的数字进行加减运算。对于那些复杂的运算他也只能请教算盘专家。十进制系统，由印度发明于公元600年左右，它是定量推理的革命。它仅仅使用了10个符号，甚至可以很简洁地写出很大的数字，它使得后面演示的算法基本步骤变得非常有效率。尽管如此，由于传统语言的阻碍，在很长一段时间内它都不被人们所熟知。对它的传播产生重大影响的是一本教材，这本书由一个居住于巴格达的阿拉伯人Al Khwarizmi写于19世纪。（译者注：Alkhwarizmi（约780约850），生于 Khiva，卒地不详。回教的数学家，代数与算术的整理者，被誉为“代数之父”。Al
4、khwarizmi 离开了家乡，前往当时的学问中心巴格达，服务於回教势力极盛的 al-Mamun 及 al-MutaAiw 宫廷。他引进了印度数字，发展算术，后经 Fibonacci（11701250年）引介到欧洲，逐渐代替了欧洲原有的算板计算及罗马的记数系统。欧洲人就把 Alkhwarizmi 这个字拉丁化，称用十进位印度阿拉伯数字来进行有规则可寻之计算的算术为 Algorithm。後来算术转用其他的字（如 arithmetic）来表示，而 algorithm 现在则成为电脑科学的行话电脑所赖以计算的运算法则。）Al Khwarizmi展示了数字的加、减、乘、除的基本方法，甚至展示了如何求平
5、方根和。这些方法精准、明确、有法可寻、具有效率、正确而且简单，它们叫“运算法则”，在很多世纪之后，十进制系统最终被欧州采用，而这个新名词也是用于纪念这位哲人的。从那以后，十进制系统和它的数字运算法则在西方文明扮演了一个十分重要的角色。它促进了科学和技术的发展；加速了工业和商业的进步。很久以后，随着计算机的出现，它又明确地表达了位值系统中的位、单词和算法单元。科学家不断发展出复杂算法用于解决各类问题，并不断发明新奇的应用软件，最终改变了世界。（译者注：考虑到Al Khwarizmi没见过电脑，所以有些地方把algorithms译为运算法则而不是算法）0.2 走进Fibonacci如果没有一个人的
6、努力，Al Khwarizmi的工作将无法立足于西方，15世纪意大利数学家Leonardo Fibonacci（斐波纳契）看到位值系统的潜力，并对它进行了进一步地发展和宣传。但今天Fibonacci被大多数人所知是因为它著名的数列0,1,1,2,3,5,8,13,21,34,每一个数的值都是它的前两项之和。更为正式地，Fibonacci数列Fn由以下简单的规则产生没有任何一个数列象它这样被如此广泛地学习和应用于不同的领域：生物，人口统计学，艺术，建筑，音乐，列出来的只是很少一部分。它跟2的方幂一样，都是计算机科学家喜欢的序列。实际上，Fibonacci数的增长几乎和2的方幂一样快：例如，F(3
7、0)起过100万，F(100)已经达到21位数的长度！F(n)2(0.694n)（参考练习0.3）（译者注：博客还是有局限性的，无法写数学公式，这里的上标和下标用括号括起来进行简单替代）但F(100)或F(200)的精确值是什么呢？Fibonacci本人也很想知道这个答案。要回答它，我们需要给第n个Fibonacci数设计一个算法。指数算法第一种想法是盲目地使用递归来实现F(n)。下面是实现代码，本书从始至终都使用伪代码：function fib1(n)if n = 0: return 0if n = 1: return 1return fib1(n - 1) + fib1(n - 2)无论何
8、时，当我们有了一个算法，都要提三个问题1. 它是否正确？2. 当确定函数的n值时，需要花费多少时间？3. 可以做得更好吗？第一点是毫无实际意义的，这个算法精确地表现了Fibonacci所定义的F(n)。但第二点需要一个答案。假设T(n)是计算filbl(n)所需的运算次数；如何分析这个函数呢？首先，当n小于2时，执行两步之后，这个过程将立即结束。所以：T(n)2 当 n1 时当n为更大的值时，fibl会有两个递归调用，花费的时间分别为T(n-1)和T(n-2)，把三个步骤加起来，得出最终结果：T(n)=T(n-1)+T(n-2)+3 当 n1 时参照F(n)的递归性质，很快可以发现T(n)F(
9、n)。这是很坏的消息：算法耗费时间的增长跟Fibonacci数列一样快！T(n)为n的指数，这意味着这个算法并不实用，除非n的值很小。让我们把这个指数时间说得更具体些。为了计算F(200) ，fibl算法将执行T(200)F(200) 2(138)（译者注：表示2的138次方）个运算次数。在电脑上运算需要花费多长时间呢？当今，世界上最快的电脑是NEC Earth Simulator，它每秒运算40万亿次。就算是在这样的机器上fib1(200)最少也需要花费2(92)秒。这意味着如果我们今天开始计算，直到太阳变为红巨星后还没得到结果。（译者注：大概是说太阳毁灭了还没算完）但技术在不断进步-计算机
10、的速度每隔18个月会翻一翻，这种现象被称为摩尔定律。有了这个非凡的增长速度，或许fibl明年将运行在更快的机器上。Fibl(n)的运行时间约等于2(0.694n)1.6(n)，所以，F(n+1)所花的时间是F(n)的1.6倍。而在摩尔定律下，计算机的运算速度每年大约会有1.6倍的增长。所以如果我们使用今天的技术来计算F(100)，那么明天将可以计算F(101)，后年就是F(102)。也就是说，每年可以增加一个Fibonacci数字！这就是让人诅咒的指数时间。（译者注：的确是写得很有意思，很有想象力）简而言之，我们天真的递归算法是正确的，但效率令人绝望，我们可以做得更好吗？多项式算法让我们尝试理
11、解为什么fibl如此之慢。图0.1显示了单独调用fib1(n)所触发的递归调用的瀑布图形。注意，有很多重复的计算！更明智的方法是存储中间结果-得到F(0)，-F(0)，-F(n-1)的值时就进行存储。function fib2(n)if n = 0 return 0create an array f0 . nf0 = 0, f1 = 1for i = 2 . n:fi = fi - 1 + fi - 2return fn和fib1一样，这个算法的正确性是不证自明的，因为它直接使用了Fn的定义。它会花费多少时间呢？它只在循环内部执行单一计算并执行n-1次。因此使用fib2的运算次数是n的线性值。
12、从指数到多项式，在运行时间上取得了巨大的突破。现在用它来计算F200甚至F2000000都是合理并完美的。这样的场景将贯穿本书，正确的算法可以改变一切。更仔细地分析岂今为止，我们所统计的是程序执行时每个算法的基本运算次数，并假设每次运算耗费的是一个时间常量。这种简化是有好处的。毕竟，处理器的指令系统里有各种各样的基本基元-分支，存储，对比数字，简单算术等等-把这些基本操作区分开来远比把它们混在一起更为方便。但回头看看前面讨论的Fibonacci算法，我们把一个基本步骤想象得过于自由。如果只是一些很小的数字进行相加，如32bit数字，这时把加法做为一个单独的计算步骤是合理的。但第n阶Fibona
13、cci数字的长度接近0.694n位，当n增长时，数字的长度将超过32。任何大数的算术运算都不可能在恒定时间的一个步骤内执行完毕。我们需要重新审视之前对运算时间所做的评估，并使它变得更为合理。更仔细地分析岂今为止，我们所统计的是程序执行时每个算法的基本运算次数，并假设每次运算耗费的是一个时间常量。这种简化是有好处的。毕竟，处理器的指令系统里有各种各样的基本基元-分支，存储，对比数字，简单算术等等-把这些基本操作区分开来远比把它们混在一起更为方便。但回头看看前面讨论的Fibonacci算法，我们把一个基本步骤想象得过于自由。如果只是一些很小的数字进行相加，如32bit数字，这时把加法做为一个单独的
14、计算步骤是合理的。但第n阶Fibonacci数字的长度接近0.694n位，当n增长时，数字的长度将超过32。任何大数的算术运算都不可能在恒定时间的一个步骤内执行完毕。我们需要重新审视之前对运算时间所做的评估，并使它变得更为合理。我们在第一节中看到，两个n位的数字相加所需时间大概跟n成比例；只要你回想小学所学的加法过程就不难理解一次可以处理一个数字。因而，fib1执行Fn的加法，实际上使用的基本步骤大概跟nFn成比例。同样，fib2所执行的步骤大概跟n的平方成比例，因此n的多项式并不比指数更为高级。但这些正确的时间的分析并不能抹杀我们所做的改进。但我们可以比fib2做得列好吗？这一点可以查看练习
15、0.4。0.3 大O表示法我们刚才已经看到草率地对运行时间进行分析会导致结果中出现让人不能接受的错误。但错误还是会存在的：不可能做到完全正确。一个有见解的分析是基于正确的简化之上的。前面的基本运算步骤这个术语表达了运算时间。而一个步骤所耗费的时间主要依赖于特定的处理器甚至依赖于缓存策略等（这样在不同计算机上执行所得到的结果会稍有不同）。如果按照这种具体架构的方式来进行分析，我们的任务会非常复杂且难以让人接受。得出的结果也不能适用于多台计算机。因此，找到一个通用的，独立于机器特性的描述算法效率的方法就变得非常有意义。最终，我们通过计算基本运算步骤的次数做为运行时间的依据，即是问题规模的某个函数。这种简化导致另一种结果，而不是报告一个算法需要花费多少时间。如输入参数为5n3+4n+3个步骤，可以舍弃低阶项如4n和3（它们对n的增长毫无意义），甚至高阶项的系数5也可以舍弃，也就是说一个算法花费的时间为O(n3)（称为“big oh of n3）（译者注：oh表示字母O）。是时候给这个符号下个精确的定义了。下文中，如果把f(n)和g(n)做为两个算法在问题规模n下的运行时间。f(n)和g(n)是从正整数到正实数的函数。当存在一个正常数使得f(n)cg(n)，我们说f=O(g)（这意味着f的增长不比g快）。f=O(g)是非常
