空間換時間，把遞歸的時間復雜度降低到O(2n)

　　遞歸算法的時間復雜度除非只有前兩項，否則都不是線性的，并且相當耗費內存。我們用最常見的的fibonacci數列來說明：

function fibonacci(n){if( n === 0 || n === 1){return n;} else {return fibonacci(n - 1) + fibonacci(n - 2);}
}

?　　這是一種最常見的寫法，這種寫法極其耗費內存，當參數n大于30時，就會明顯感覺到花的時間比較長，如果n等于100，瀏覽器極有可能會崩潰掉。

　　我們來分析一下耗費內存和時間原因：先將要計算的變量值存到堆棧中，不停地使用棧，保存現場，直到遞歸結束條件滿足時，才從堆棧中取出要計算的變量值，再一一恢復現場，計算得到最終結果。

　　我們通過一張圖來看一下這個遞歸的調用過程：

　　我們可以看到，當n為4時，一共進行了12步運算，其中第6、8、9、10、11步是重復的。正是這些重復的地方造成了這個遞歸的低效。

　　既然找到了原因所在，那么我們怎么來改進呢？

　　從原因下手，原因是之前的計算結果沒有保存，造成了重復計算，那么我們就把之前的計算結果用一個變量保存起來，修改后的代碼如下：

var fibonacci=(function(){var temp={},value;function f(n){if(n in temp){value=temp[n];} else {if( n === 0 || n === 1){value = n;} else {value = f(n - 1) + f(n - 2);}temp[n] = value;}return value;}return f;
})();

　　這里我們引入了一個變量temp來存儲前面的計算結果，這種做法就是以空間換時間的做法。由于遞歸總是要到達最底層，然后再回到最頂層，所以時間復雜度最小為O(2n)，我們修改后的遞歸算法時間復雜度即為O(2n)。

　　最后，我們來測試一下計算n為100的情況時間和計算次數：

　　我們可以看到，時間很短，計算次數只有199次。如果用沒有優化的代碼，我的瀏覽器會崩潰掉。

　　希望本文對大家有所幫助，歡迎留言討論。

　　本文首發博客園：http://jscode.cnblogs.com，轉載請注明出處。