我们为什么要思考算法

源头

“算法”的中文最早出现在中国汉代的数学名著《周髀算经》中。《周髀算经》卷上有:“数之法出于圆方。圆出于方,方出于矩。矩出于九九八十一”。意思是: 算数的方法都出于对圆、对方的计算,其中圆出于方(圆形面积=外接正方形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 次方个斐波那契数。

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

结语

对算法效率的追求,在任何场景中,都可以给你带来意想不到的惊喜。对于产品的突破、开销的降低、技术气氛的凝聚,还有什么方式比思考与重视算法来的更加有效与唯美呢?

作者:华傲数据算法部

声明:本文部分内容借鉴于T.H.Cormen 等著《算法导论》与邹恒明著《算法之道》,特此感谢与声明。图片源自网络。

你也许感兴趣的:

共有 1 条讨论

  1. dongguangming 对这篇文章的反应是赞一个

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注