[600769股吧]我们为什么要思考算法

源头

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

ChineseteachersbringtheartofmathstoEnglishschos

在西方，真实推进算法传达的是一个居住在巴格达的阿拉伯人，AlKhwarizmi，他引进了印度更为先进的十进制数字体系。AlKhawarizmi展现了加、减、乘、除，乃至平方根和圆周率π的核算进程。这些进程的特点是：简略、无歧义、有用、有穷进程、正确。数百年后，当十进制阿拉伯数字体系在欧洲广泛运用时，人们便创造出AlKhwarizmi的拉丁化写法“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的EarthSimator的30倍，但这也只是意味着Roadrunner比后者在相同的时刻下以指数级复杂度多算7个数。但假如运用log(n)复杂度的算法，那么Roadrunner可多算10的30次方个斐波那契数。

所以，算法书其实不全是用来垫咖啡杯的……改善算法比起提高硬件速度的作用，仍是很明显的，不是吗。

结语

对算法功率的寻求，在任何场景中，都能够给你带来意想不到的惊喜。关于产品的打破、开支的下降、技能气氛的凝集，还有什么方法比考虑与注重算法来的愈加有用与唯美呢？

声明：本文部分内容借鉴于T.H.Cormen等著《算法导论》与邹恒明著《算法之道》。

Via:36大数据
金融工程,数学算法