程序设计经典名著--算法之美中文译文.doc

第0章
序言
环顾四周。计算机和网络无处不在，它为复杂的人类活动纺织了一张巨大的网：教育，商业，娱乐，研究，制造业，卫生管理，人类通讯甚至战争。支撑起这种惊人增长的是两个主要的科技：高速发展的微电子技术和芯片设计已经带给我们越来越快的计算机硬件。
这本书讲述的是另一个知识产业的故事：计算机革命的动力：高效算法。这是令人着迷的故事。请搬好凳子慢慢听我讲来！
0.1     书籍和运算法则
有两个想法改变了世界。1448年德国美因兹，一个名叫Johann Gutenberg的金匠发现了把活动金属块这在一起来印刷书籍的方法。随着知识不断传播，黑暗时代从此结束，人类思想被完全解放，科学和技术迎来光明，工业革命爆发。很多历史学家把这归功于活版印刷术，设想一下只有极少数人能够阅读知识这个世界会是什么样子！但还有一部分人这一切的关键不是活版印刷术而是运算法则。
今天我们已经习惯于使用阿拉伯数字来书写数字，象Gutenberg那样把1448写成MCDXLVIII是非常容易被忘记的（译者注：MCDXLVIII是罗马数字，它代表1448，罗马数字是欧洲在阿拉伯数字（印度数字）传入之前使用的一种数码，现在应用较少。它的产生晚于中国甲骨文中的数码，更晚于埃及人的十进位数字。但是，它的产生标志着一种古代文明的进步）。你怎么样去对两个罗马数字进行相加呢？什么是MCDXLVIII + DCCCXII呢？（再想想如何对它们相乘。）甚至象Gutenberg这样聪明的人大概也只会使用手指头对两个很小的数字进行加减运算。对于那些复杂的运算他也只能请教算盘专家。
十进制系统，由印度发明于公元600年左右，它是定量推理的革命。它仅仅使用了10个符号，甚至可以很简洁地写出很大的数字，它使得后面演示的算法基本步骤变得非常有效率。尽管如此，由于传统语言的阻碍，在很长一段时间内它都不被人们所熟知。
对它的传播产生重大影响的是一本教材，这本书由一个居住于巴格达的阿拉伯人Al Khwarizmi写于19世纪。（译者注：Alkhwarizmi（约780～约850），生于 Khiva，卒地不详。回教的数学家，代数与算术的整理者，被誉为“代数之父”。Alkhwarizmi 离开了家乡，前往当时的学问中心巴格达，服务於回教势力极盛的 al-Mamun 及 al-MutaAiw 宫廷。他引进了印度数字，发展算术，后经 Fibonacci（1170～1250年）引介到欧洲，逐渐代替了欧洲原有的算板计算及罗马的记数系统。欧洲人就把 Alkhwarizmi 这个字拉丁化，称用十进位印度阿拉伯数字来进行有规则可寻之计算的算术为 Algorithm。後来算术转用其他的字（如 arithmetic）来表示，而 algorithm 现在则成为电脑科学的行话──电脑所赖以计算的「运算法则」。）Al Khwarizmi展示了数字的加、减、乘、除的基本方法，甚至展示了如何求平方根和π。这些方法精准、明确、有法可寻、具有效率、正确而且简单，它们叫“运算法则”，在很多世纪之后，十进制系统最终被欧州采用，而这个新名词也是用于纪念这位哲人的。
从那以后，十进制系统和它的数字运算法则在西方文明扮演了一个十分重要的角色。它促进了科学和技术的发展；加速了工业和商业的进步。很久以后，随着计算机的出现，它又明确地表达了位值系统中的位、单词和算法单元。科学家不断发展出复杂算法用于解决各类问题，并不断发明新奇的应用软件，最终改变了世界。（译者注：考虑到Al Khwarizmi没见过电脑，所以有些地方把algorithms译为运算法则而不是算法）
0.2 走进Fibonacci
如果没有一个人的努力，Al Khwarizmi的工作将无法立足于西方，15世纪意大利数学家Leonardo Fibonacci（斐波纳契）看到位值系统的潜力，并对它进行了进一步地发展和宣传。
但今天Fibonacci被大多数人所知是因为它著名的数列
0,1,1,2,3,5,8,13,21,34,…,
每一个数的值都是它的前两项之和。更为正式地，Fibonacci数列Fn由以下简单的规则产生

没有任何一个数列象它这样被如此广泛地学习和应用于不同的领域：生物，人口统计学，艺术，建筑，音乐，列出来的只是很少一部分。它跟2的方幂一样，都是计算机科学家喜欢的序列。
实际上，Fibonacci数的增长几乎和2的方幂一样快：例如，F(30)起过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 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)
无论何时，当我们有了一个算法，都要提三个问题
1.         它是否正确？
2.         当确定函数的n值时，需要花费多少时间？
3.         可以做得更好吗？
第一点是毫无实际意义的，这个算法精确地表现了Fibonacci所定义的F(n)。但第二点需要一个答案。假设T(n)是计算filbl(n)所需的运算次数；如何分析这个函数呢？首先，当n小于2时，执行两步之后，这个过程将立即结束。所以：
T(n)≤2 当 n≤1 时
当n为更大的值时，fibl会有两个递归调用，花费的时间分别为T(n-1)和T(n-2)，把三个步骤加起来，得出最终结果：
T(n)=T(n-1)+T(n-2)+3 当 n>1 时
参照F(n)的递归性质，很快可以发现T(n)≥F(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)秒。这意味着如果我们今天开始计算，直到太阳变为红巨星后还没得到结果。（译者注：大概是说太阳毁灭了还没算完）
但技术在不断进步----计算机的速度每隔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数字！这就是让人诅咒的指数时间。（译者注：的确是写得很有意思，很有想象力）
简而言之，我们天真的递归算法是正确的，但效率令人绝望，我们可以做得更好吗？
多项式算法
让我们尝试理解为什么fibl如此之慢。图0.1显示了单独调用fib1(n)所触发的递归调用的瀑布图形。注意，有很多重复的计算！

更明智的方法是存储中间结果---得到F(0)，-F(0)，．．．-F(n-1)的值时就进行存储。
function fib2(n)
if n = 0 return 0
create an array f[0 ... n]
f[0] = 0, f[1] = 1
for i = 2 ... n:
f[i] = f[i - 1] + f[i - 2]
return f[n]
和fib1一样，这个算法的正确性是不证自明的，因为它直接使用了Fn的定义。它会花费多少时间呢？它只在循环内部执行单一计算并执行n-1次。因此使用fib2的运算次数是n的线性值。从指数到多项式，在运行时间上取得了巨大的突破。现在用它来计算F200甚至F2000000都是合理并完美的。
这样的场景将贯穿本书，正确的算法可以改变一切。
更仔细地分析
岂今为止，我们所统计的是程序执行时每个算法的基本运算次数，并假设每次运算耗费的是一个时间常量。这种简化是有好处的。毕竟，处理器的指令系统里有各种各样的基本基元----分支，存储，对比数字，简单算术等等--------把这些基本操作区分开来远比把它们混在一起更为方便。
但回头看看前面讨论的Fibonacci算法，我们把一个基本步骤想象得过于自由。如果只是一些很小的数字进行相加，如32bit数字，这时把加法做为一个单独的计算步骤是合理的。但第n阶Fibonacci数字的长度接近0.694n位，当n增长时，数字的长度将超过32。任何大数的算术运算都不可能在恒定时间的一个步骤内执行完毕。我们需要重新审视之前对运算时间所做的评估，并使它变得更为合理。

更仔细地分析
岂今为止，我们所统计的是程序执行时每个算法的基本运算次数，并假设每次运算耗费的是一个时间常量。这种简化是有好处的。毕竟，处理器的指令系统里有各种各样的基本基元----分支，存储，对比数字，简单算术等等--------把这些基本操作区分开来远比把它们混在一起更为方便。
但回头看看前面讨论的Fibonacci算法，我们把一个基本步骤想象得过于自由。如果只是一些很小的数字进行相加，如32bit数字，这时把加法做为一个单独的计算步骤是合理的。但第n阶Fibonacci数字的长度接近0.694n位，当n增长时，数字的长度将超过32。任何大数的算术运算都不可能在恒定时间的一个步骤内执行完毕。我们需要重新审视之前对运算时间所做的评估，并使它变得更为合理。
我们在第一节中看到，两个n位的数字相加所需时间大概跟n成比例；只要你回想小学所学的加法过程就不难理解一次可以处理一个数字。因而，fib1执行Fn的加法，实际上使用的基本步骤大概跟nFn成比例。同样，fib2所执行的步骤大概跟n的平方成比例，因此n的多项式并不比指数更为高级。但这些正确的时间的分析并不能抹杀我们所做的改进。
但我们可以比fib2做得列好吗？这一点可以查看练习0.4。
0.3 大O表示法
我们刚才已经看到草率地对运行时间进行分析会导致结果中出现让人不能接受的错误。但错误还是会存在的：不可能做到完全正确。一个有见解的分析是基于正确的简化之上的。
前面的基本运算步骤这个术语表达了运算时间。而一个步骤所耗费的时间主要依赖于特定的处理器甚至依赖于缓存策略等（这样在不同计算机上执行所得到的结果会稍有不同）。如果按照这种具体架构的方式来进行分析，我们的任务会非常复杂且难以让人接受。得出的结果也不能适用于多台计算机。因此，找到一个通用的，独立于机器特性的描述算法效率的方法就变得非常有意义。最终，我们通过计算基本运算步骤的次数做为运行时间的依据，即是问题规模的某个函数。
这种简化导致另一种结果，而不是报告一个算法需要花费多少时间。如输入参数为5n^3+4n+3个步骤，可以舍弃低阶项如4n和3（它们对n的增长毫无意义），甚至高阶项的系数5也可以舍弃，也就是说一个算法花费的时间为O(n^3)（称为“big oh of n^3）（译者注：oh表示字母O）。
是时候给这个符号下个精确的定义了。下文中，如果把f(n)和g(n)做为两个算法在问题规模n下的运行时间。
f(n)和g(n)是从正整数到正实数的函数。当存在一个正常数使得f(n)≤c·g(n)，我们说f=O(g)（这意味着f的增长不比g快）。
f=O(g)是非常松散的类似于“f≤g”。它跟平常使用的符号≤并不相同，这是因为常数c的存在，例如10n=O(n)。可以忽略这个常数值。例如，假设我们为一个特定的计算任务选定了两个算法。一个使用f1(n)=n^2步骤，而另一个使用f2(n)=2n+20个步骤（如图0.2）。哪个更好呢？好，这取决于n的值。当n<5时，f1更小；随后，f2明显胜出。在本例中，当n增长时，f2的增长率更小，因此它更好。

这种优越性用大O表示法：f2=O(f1)更容易体现出来，因为下式中对于所有n来说：

(译者注：把n的最小值1代入，可得到结果22，当n越大结果越小，所以得到<=22的结果)
从另一方面来说，f1≠O(f2)，因为f1(n)/f2(n)=n^2/(2n+20)可以无限大，没有常数c也可以下这样的定义。
现在出现了另一个算法，需要使用f3(n)=n+1个步骤。它比f2好吗？这是肯定的，但它们的速度比是一个常数。为了从更高的高度看问题，当两个函数的不同之处只是乘以了一个常数，那么我们认为这两个常数相等。
使用大O表示法，我们说f2=O(f3)：

当然，f3=O(f2)，所以这一次，c=1。
O(.)仅仅表示了≤的类似体，我们也可以表示≥和=的类似体如下：
f=Ω(g) 表示 g=O(f)
f=θ(g)表示f=O(g)和f=Ω(g)
在上一个例子中，f2=θ(f3)并且f1=Ω(f3)。
大O表示法可以让我们站在更高的地方看问题。当面对3n^2+4n+5这样复杂的函数，我们可以简单地使用O(f(n))或f(n)来代替。此例中我们可以使用O(n^2)，因为二次幂在整个多项式和中占主导地位。下面的一些常用的简化规则可以帮助我们忽略不受控制的项目。
l         常数系数可以忽略：14n^2简化为n^2；
l         当a>b，则n^a支配（dominate）n^b：n^2支配n；
l         任何指数幂都支配多项式：3^n支配n^5（它也支配2^n）
l         任何多项式都支配对数：n支配(log(n))^3，这意味着n^2支配nlogn。
不要误解这种对于常数的骑士态度（译者注：意为傲慢的态度）。程序员和算法开发者对常数很感兴趣，并很愿意为了系数2整夜不眠来设计一个算法以使程序运行得更快。但如果站在本书的高度理解算法，不可能不涉及简单的大O表示法。
第一章 数论算法
本章所讨论的是对两个古典问题进行生动的对比。它们看上去非常相似：
l         因式分解（Factoring）：给定一个数字N，将其表示成素数的乘积。
l         素属性（Primality）：给定一个数字N，判断它是否是素数。
因式分解比较困难。尽管几个世纪以来世界上最聪明的数学家和科学家付出了很多努力，但分解一个数字N的最快的算法复杂度还是N位数的指数幂。
另一方面，我们可以很快地判断出N是否是素数！并且更有趣的是两个有密切联系的问题间的不对等：一个很难而另一个很容易。今天，两个问题的这种特性成为当今信息安全的核心基础。
在讲解这个问题的过程中，需要开发各种各样的数字计算的算法。从基本的算术开始是最为适合的，因为我们知道，“algorithms”这个单词最初只是解决这类问题的手段。
1.1 基本算术
1.1.1 加法
我们很小的时候，在学习加法运算时从来没有想过为什么要这样做。现在回过头来对它做进一步地了解。
十进制数字有一个基本属性：
任意三个个位数相加，其结果的最大值的位数不超过2位。
检验一下：9+9+9=27，结果为2位。这个规则不仅适用于十进制数，而且适用于所有进制（b>=2）。在二进制中，三个个位数的和的最大值为3，它是一个2位数字。（译者注：二进制的3个1相加结果为3，即二进制的11）。
底数和对数
自然地，这里没有提到10—我们正好有10个手指头，10也是数字计算中进入下一个级别的停顿点。玛雅人发明了一个类似位值系统，它是20进制的。当然，今天的计算机是用二进制来表现数字的。
基于b进制的正数N需要使用多少个位来表现呢？我们来看看---基于b进制的k位数最大值为b^k-1；例如，十进制中，三位数的最大值为999=10^3-1。使用[logb(N+1)]可以得出k的值（约等于logbN位，把1省略去），这样就可以使用以b为底的N的对数。
当改变底数时，数字的位数会改变多少呢？当底数由a变为b时，我们回顾关于对数的规则可以得出：logbN=(logaN)/(logab)。数字N的位数以a为底时相当于以b乘以一个常数因子logab。对于大O表示法来说，底数没有任何影响，我们只是简单地写为O(logN)。一般情况下，不需指定底数，这时我们把它当为log2N。
顺便提一下，这个logN函数多次隐蔽地出现在本书中，下面是一此样本：
1.       logN is, of course, the power to which you need to raise 2 in order to obtain N.
2.       Going backward, it can also be seen as the number of times you must halve N to get down to 1. (More precisely: dlogNe.) This is useful when a number is halved at each iteration of an algorithm, as in several examples later in the chapter.
3.       It is the number of bits in the binary representation of N. (More precisely: [log(N+1)].)
4.       It is also the depth of a complete binary tree with N nodes. (More precisely: [logN].)
这个简单的规则给了我们一个方法来对两个数相加：让它们的右边对齐，并从左到右对数字逐个进行加法运算，当有溢出时则进位。因为个位数的和最多为两位数，所以进位始终是个位数，在一些特定步骤中，三个个位数被相加。下面的例子二进制演示了53+35。

通常我们会给出算法的伪代码，但此例大家已经非常熟悉，我们就不再重复了，而是直接分析它的效率。
给定两个二进制数x和y，对两个数相加的算法需要花费多少时间呢？这一类的问题在本书中将贯穿始终我们希望用问题规模的函数来回答这个问题：数字x和y的位数，也就是输入它们需要敲键的次数。
假设x和y的长度都是n位；本章将全部使用n做为数字的长度。那么x + y的长度最多为n+1，并且每个位相加的运算时间为固定的。那么两数相加算法所耗费的时间为c0+c1n，c0和c1是常数。换句话说，这是线性的。我们站在更高的层面看问题，不需要考虑其精确性，舍去c0和c1，从而得到运行时间为O(n)。
现在已经有了一个算法并且知道了它的运行时间，但我们还是不可避免地会问：还能做得更好吗？
还会有更快的算法吗？（这是另外一个经常要提到的问题）其实，答案非常简单：为了把两个n位数字相加，我们至少要阅读它们并写下答案，这正好需要n次操作。所以相加算法是最优的，它是常数的倍数。
一些读者可能会对一个问题感到困惑：为什么是O(n)次运算？今天的计算机不是只使用一条指令进行二进制加法吗？这有两个答案。第一，对于今天的32位电脑来说，对一个字节长度的整数进行相加当然只是使用一条指令。但我们在本章后面将会看到，经常并且必须要处理更大的，甚至太到几千个位的数字。对这么大的数字进行加法或者乘法运算必须一点点地运算。第二，如果我们想理解算法，学习当今计算机的那些由硬件编码组成的基础算法是非常有意义的。为此，我们将聚集于算法的位复杂度（bit complexity，译者注：不知道怎么翻译这个术语，只好按字面意思翻译了），数字中的单个位的初等运算，因为这个数字反映了实现算法所需要的硬件、晶体管和导线。