初入算法的人都会听过斐波那契数列，看看维基百科的定义：
斐波那契数列（意大利语 Successione di Fibonacci），又译为费波拿契数、斐波那契数列、费氏数列、黄金分割数列。
在数学上，费波那契数列是以递归的方法来定义：
用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
如果以编程方式来获取第 N 个数的值，我很自然的就想到递归
// in javascript
function fibonacci(n){
if(n <= 0) return 0;
if(n == 1) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
看着是不是很简洁？ 嗯，很标准，边界确定了，也有一步步递进的求解过程，那我们放在浏览器 console 上跑一跑，顺便看看运行时间，为此再来帮助函数
function time(fn, ...args) {
var start = new Date().valueOf();
console.log(fn(...args))
var end = new Date().valueOf();
console.log('elapsed: ' + (end - start) + 'ms');
}
先来获取 n = 10 的值，看下面的结果正常，1毫秒一开始也怎么在意。
那再来试试 n = 50的... 等了好一会 还没打印出来结果 还以为浏览器卡了！！！
这才到50， 就花去了330秒，5分多钟了喂，真可怕 !?(･_･;? 连三位数都还没到，更别说w级别以上了。
为毛会这么慢？？？ 我们以 n = 10 来分析下过程
先原谅我这丑不拉几的字迹... 沿着这个树形结构往回推进，发现Fib(8) 执行了2次，Fib(7)执行了3次，Fib(6)执行3次以上，存在着大量重复的计算，复杂度达到指数级别，而且数量级越大重复越严重。这二叉树没有满，我们按满的算那总的计算次数为 T(N) = 1 + 2 + 4 + 8 + ... + 2^10 => 2^n+1 -1 大概时间复杂度是 O( (2^N), 最牛逼的那个N次方。
换个思路
前面的递归是从第n位往回推导的，那我们正向的去一步步得出相应位置的值，就可以省去反向递归带来的大量重复操作了，也就是常说的递推，时间复杂度为 O(N) 代码如下：
// 递推
function fibonacci(n) {
if (n <= 0) return 0;
if (n == 1) return 1;
var first = 0,
second = 1,
index = 1,
fib = 0;
while (index++ < n) {
fib = first + second;
first = second;
second = fib;
}
return fib;
}
试验下, 50 几乎不耗时
慢慢往上加， 可以看到到1w的时候 js的数字已经装不下了， 但是获取第10w位置的也才需要2ms的时间。
补充@林晓池Smile 评论的说法， 以空间换时间，利用数组来存储已经计算过的斐波那契数列中的值
var memo = [];
function fibonacci(n){
if(n <= 0) return 0;
if(n == 1) return 1;
if(!memo[n])
memo[n] = fibonacci(n-1) + fibonacci(n-2);
return memo[n];
}
测试看看
可以看到相比一开始的递归，省去了很多重复的计算；但是获取第10w个数的时候堆栈就溢出了，因为即使记忆了但是还存在递归调用， 递推的方案倒是不会
调用堆栈的上限如下：
Three results:
Node.js: 11034
Firefox: 50994
Chrome: 10402
入门例子就可以体会到合理选择算法的威力了，我要继续努力~ 为分布式系统节省机器
网上对斐波那契有其他更优质的算法，但是那种数学公司俺看不懂。。。 以后再回炉重造学习高数吧。
网友评论