初入算法的人都會聽過斐波那契數(shù)列厘托，看看維基百科的定義：
斐波那契數(shù)列（意大利語 Successione di Fibonacci）稿湿，又譯為費波拿契數(shù)、斐波那契數(shù)列饺藤、費氏數(shù)列、黃金分割數(shù)列罗丰。
在數(shù)學上再姑，費波那契數(shù)列是以遞歸的方法來定義：
用文字來說，就是費波那契數(shù)列由0和1開始谜嫉，之后的費波那契系數(shù)就是由之前的兩數(shù)相加而得出凹联。首幾個費波那契系數(shù)是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
如果以編程方式來獲取第 N 個數(shù)的值沐兰，我很自然的就想到遞歸
// in javascript
function fibonacci(n){
if(n <= 0) return 0;
if(n == 1) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
看著是不是很簡潔蔽挠？ 嗯瓜浸，很標準比原，邊界確定了，也有一步步遞進的求解過程雇寇，那我們放在瀏覽器 console 上跑一跑蚌铜，順便看看運行時間，為此再來幫助函數(shù)
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分多鐘了喂，真可怕 !?(?_?;? 連三位數(shù)都還沒到婴栽，更別說w級別以上了。
為毛會這么慢映皆？轰枝？？ 我們以 n = 10 來分析下過程
先原諒我這丑不拉幾的字跡... 沿著這個樹形結構往回推進鞍陨，發(fā)現(xiàn)Fib(8) 執(zhí)行了2次，F(xiàn)ib(7)執(zhí)行了3次缭裆，F(xiàn)ib(6)執(zhí)行3次以上，存在著大量重復的計算澈驼，復雜度達到指數(shù)級別缝其，而且數(shù)量級越大重復越嚴重。這二叉樹沒有滿氏淑，我們按滿的算那總的計算次數(shù)為 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的數(shù)字已經(jīng)裝不下了， 但是獲取第10w位置的也才需要2ms的時間线罕。
補充@林曉池Smile 評論的說法钞楼， 以空間換時間，利用數(shù)組來存儲已經(jīng)計算過的斐波那契數(shù)列中的值
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個數(shù)的時候堆棧就溢出了刻蟹，因為即使記憶了但是還存在遞歸調用嘿辟， 遞推的方案倒是不會
調用堆棧的上限如下：
Three results:
Node.js: 11034
Firefox: 50994
Chrome: 10402
入門例子就可以體會到合理選擇算法的威力了痢艺，我要繼續(xù)努力~ 為分布式系統(tǒng)節(jié)省機器
網(wǎng)上對斐波那契有其他更優(yōu)質的算法介陶，但是那種數(shù)學公司俺看不懂。舌缤。某残。 以后再回爐重造學習高數(shù)吧国撵。
