我们为什么要思考算法

源头

“算法”的中文最早出现在中国汉代的数学名著《周髀算经》中。《周髀算经》卷上有：“数之法出于圆方。圆出于方，方出于矩。矩出于九九八十一”。意思是：算数的方法都出于对圆、对方的计算，其中圆出于方(圆形面积=外接正方形x圆周率/4)，方出于矩(正方形源自两边相等的矩)，矩的计算出于九九八十一 (长乘宽面积的计算依自九九乘法表)。追溯回去，在春秋战国时代，《九九乘法歌诀》已经开始流行起来。话说，自从卡梅伦被8×9等于多少问呆以后，英国教育部就开始聘请上海的小学数学老师赴英训练小九九了……

Chinese teachers bring the art of maths to English schools

我们为什么要思考算法

在西方，真正推动算法传播的是一个居住在巴格达的阿拉伯人，Al Khwarizmi，他引进了印度更为先进的十进制数字系统。Al Khawarizmi展示了加、减、乘、除，乃至平方根和圆周率π的计算步骤。这些步骤的特点是：简单、无歧义、有效、有穷步骤、正确。数百年后，当十进制阿拉伯数字系统在欧洲广泛应用时，人们便创造出Al Khwarizmi 的拉丁化写法“Algorithm”，来描述这种有规可循的数字计算行为。

算法的定义

究竟什么是算法呢，字面理解，就是计算的办法或法则。这里的计算不单指加减乘除等算术运算，而是广义的做任何事情的计算。办法和法则，则意味着使用它可以解决眼前的问题。

就拿我们喜闻乐见的世界杯比赛来说，每四年一届比赛的目的就是选出此时世界上踢球最牛掰的那个国家。在200多个国家里头，如果用单循环联赛赛制，也就是每个队都必须和另外所有队踢一场，以此决定本队成绩，假设每隔三天踢一场，最快也要600来天。怎么样，累觉不爱吧，还是广场舞来的更收放自如些。对于比赛组织者来说，明智的策略当然是先在几个大洲里选出几个屈指可数的球队，然后大家聚在一起，一个月内论出高下，这时甚至还要再分成几个组，每组最强的几个队才能突出重围，踏上冠军之路。

道理上来讲，最好的球队，无论哪种赛制，总是会脱颖而出的；而上述这种优中选优的方式，难度和开销就降低许多了。上述过程有一个特定叫法：分治，也就是将一个大问题（寻找全世界的最佳球队），分解成多个类型相同但规模更小的问题（寻找一个大洲的最佳球队），如果小问题得以解决，那么大问题就更加容易解决了（各大洲最佳球队PK一下，就知道世界冠军的奖杯，花落谁家了）。这只是生活中众多算法应用的一个例子，那么由事实到抽象拔高出来一个完备的字典式定义，对应用和分析者来说，其实无太多必要。事实上，算法的定义也因看待的角度不同而不同。

如果你是个哲学家：算法是解决一个问题的抽象行为序列。

如果你是个码农：算法是一个计算过程，它接受一些输入，并产生某些输出。

如果你喜欢高大上：算法是解决一个精确定义的计算问题的工具。

但他们共同强调了一点：算法的不变式，即算法必须能够让人一步一步照着执行。

算法的核心

算法是解决问题的办法或法则。但解决一个问题不一定只有一种办法，不同的办法之间便有了好坏之分。对于解决同一个问题的不同算法，我们如何比较它们的好坏呢？

能够比较的东西当然很多，如模块性、正确性、可维护性、健壮性、友好性、简易性、可扩展性和可靠性等，但这些并不是算法设计与分析中最为关心的问题。但它们更加像是人类附加在算法上的外部属性，因为它们通常依赖于使用或实现算法的人员的其他方面素质：理解力、表述力、编程水平、数据结构的运用与设计技巧等。

那么算法的核心或灵魂是什么呢？也许您已经可以猜到：速度。也就是其解决问题的速度。因为速度往往是区分可行和不可行方案的分水岭。例如，一个让人等上很多年才能运行结束的算法，就是再正确，也不会令我们满意。从实际意义上看，这种算法的正确和不正确并无太大的本质区别。

如果一个算法在你的改进下，效率提高了成百上千倍，则当你坐在显示屏前，所获得的快感不会亚于很多其他的事情。

堆机器还是拼算法

说到提升速度，真壕们会不约而同的移步华强北，血拼内存处理器。然而，计算机速度的增长可以多大程度上解决一些简单问题呢？我们来看一个经典的例子吧。

我们有一个描述兔子增长数量的模型：

原点：一对雌雄兔子

规律：每对兔子每月产下一对兔子，且一生只能生产两次，而且第二次生产后老死。（我们这里假设产下的每对兔子都继续正常繁衍，方舟子及果壳知识帝请绕路……）我们为什么要思考算法

如果定义在第n个月的兔子数量为F(n)，那么F(n)个兔子中包含这个月新生的兔子（也就是（第n-1月）兔子总数F(n-1)），和上个月的新生兔子数目（因为上个月的老兔子们这个月已经死掉了），即F(n-2)。所以F(n)=F(n-1)+F(n-2)，F(n)的序列叫做斐波那契序列。

那么我们就开始算F(n)吧，比如说你想知道第30个月时的兔子数量，那么F(30)=F(29)+F(28)，那么F(29)=F(28)+F(27)，我们一直分解下去，最后变成数数一共多少个F(0)了。我们写段代码，运行它，约朋友出去打个台球，回来也许可以得到答案。若你眼光长远，想知道第300个月时的兔子数量，那么你必须要寻找其它算法了。因为F(0)的数量太庞大了。这种天真递归解法，事实上要对F(0)进行指数级次的运算。聪明的你会进一步发现斐波那契数列是一个二阶递推数列，于是最后可以用对数级次运算搞定F(300)，这里细节省略，感兴趣的话我们会在后续详细讨论。

问题是，在硬件性能愈加强悍的今天，大规模运算或者大数据的实践者们，时常认为更快的算法也许没有必要。那么我们来看斐波那契数的天真递归解法，它的时间复杂度为1.6的n次方，即计算F(n+1)的时间约是计算F(n)的1.6倍。按照摩尔定律计算性能每18个月翻倍的速度，每过一年，我们只能多计算一个未知的斐波那契数。

我们说IBM的Roadrunner 超级计算机性能为NEC的Earth Simulator的30倍，但这也仅仅意味着Roadrunner比后者在同样的时间下以指数级复杂度多算7个数。但如果使用log(n)复杂度的算法，那么Roadrunner可多算10的30次方个斐波那契数。

所以，算法书其实不全是用来垫咖啡杯的……改进算法比起提升硬件速度的效果，还是很显著的，不是吗。