Fibonacci還可以這樣算？

拋磚引玉，先從一個程式設計師都非常熟悉的斐波那契數列演算法說起，感受一下演算法的趣味。說起斐波那契，程式設計師們應該都非常熟悉了，估計是曾經我們學習遞迴時候的重點案例吧，但是除了遞迴還有沒有別的方法呢？或者說我們有沒有考慮過，結果是算對了，但是背後的效率怎麼樣呢？

方法一

先從熟悉的遞迴方法說起：

斐波那契數列應該都知道，據說大自然很多現象也都是斐波那契數，有興趣的可以去查查，這裡就不多介紹了，概念說一下，用函式公式的方式表示，大概是這個意思：

遞迴演算法程式碼最容易理解，就是反覆迭代呼叫自己往下計算，程式碼基本和上述表示式一樣，如下（本文章程式碼均用java編寫，樣例程式碼地址

https：//github。com/wangpengda/algorithm

）：

這個很容易理解，但是不知道有沒有人用這個算過F（50），我這8G記憶體，4核電腦是算了半天沒算出來。再專業一點就是看一下它的時間複雜度，仔細分析會發現是指數增長的，往後算，每多算一個數，時間是翻倍的，它的時間複雜度是O（2^n）；

01

方法二

其實斐波那契歸根結底還是個數列問題，就和我們高中學的等差數列、等比數列差不多，只是它是和用當前項的前兩項表示的，我們只需要記錄下前兩項就可以了，而不用像遞迴演算法那樣，每次都去計算前兩項，具體程式碼如下

這個演算法的時間複雜度是O（n），用這個算F（10000）基本也在1秒之內，就是這麼神奇啊。按理說這個寫法速度上已經是質的飛躍了，但是…

02

方法三

書上簡單提了一句，還可以把時間複雜度降到O（logn），不過沒有詳細贅述。好事者如我，本著不打破砂鍋的程式設計師不是好廚師的原則，繼續搜尋。不得不說，確實有大師，用矩陣的方法，也是讓我開了眼界啊，具體看下列表達式：

看著上述表示式，有什麼感想？耳邊曾經經常響起的大學課程無用論是否還在迴盪？事實證明，學校的課程還是相當有用的啊，不懂矩陣的回去查查大學線性代數， 。回過頭來再說斐波那契問題，上述表示式把數列問題就轉換成了，計算一個2*2矩陣的n-2次冪的問題，冪運算就可以用二分法運算降低時間複雜度了，簡單說一下大概思路，就比如算2的32次冪，最簡單辦法肯定是迴圈31次，用2挨個乘；二分法的意思就是2的32次冪 可以轉換為 2的16次冪乘以2的16次冪，2的16次冪 還可以轉換為 2的8次冪乘以2的8次冪，……，以此類推，大概迴圈5次即可算出最後結果。思路大概就是這麼個思路，網上程式碼是用python實現的，python裡有成熟的計算矩陣的函式，我用java實現了一下，具體程式碼如下邊兩圖所示

n比較小的時候，方法二和方法三計算時間差不多，n特別大才能看出些效果，當n=1，000，000時，方法一就不考慮了，今年應該算不出來。方法二和方法三，計算時間如下：

兩種方法計算第100萬位基本還在毫秒級別，一般情況可能第二種方法就夠用了，但是你不研究第三種方法，是體會不到第三種方法的樂趣的，呵呵~~~