周衛(wèi)星 陳思 張帆

（中國移動（深圳）有限公司，廣東深圳518048）

矩陣乘法在斐波那契數(shù)列計算中的應用

周衛(wèi)星 陳思 張帆

（中國移動（深圳）有限公司，廣東深圳518048）

本文介紹了斐波那契數(shù)列的一些算法思路，對遞歸算法、自底向上、比內(nèi)公式等算法的時間復雜度進行了分析，給出了利用矩陣乘法升維計算降低時間復雜度的方法，對比測試了各算法實現(xiàn)在不同計算量下的執(zhí)行時間。針對數(shù)據(jù)溢出，將long數(shù)據(jù)類型改進為BigInteger的數(shù)據(jù)類型,給出了大數(shù)計算下的執(zhí)行時間對比。

斐波那契；遞歸；比內(nèi)公式；矩陣

1 引言

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。它指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、……這個數(shù)列從第3項開始，每一項都等于前兩項之和。在數(shù)學上，斐波納契數(shù)列被以遞歸的方法定義如下：

2 直接遞歸實現(xiàn)

使用公式f(n)=f(n-1)+f(n-2)，依次遞歸計算，遞歸結(jié)束條件是f(1)=1，f(2)=1。

核心代碼如下：

這種方式可以以非常少的代碼實現(xiàn)第N+1項的計算，但是與之相對的，這種算法的代價也非常高，計算機每次調(diào)用函數(shù)時，為了保證函數(shù)執(zhí)行完畢，都必須將函數(shù)調(diào)用時的程序現(xiàn)場入棧保存，遞歸存在大量的自身調(diào)用，勢必會產(chǎn)生非常龐大的函數(shù)現(xiàn)場棧來記錄數(shù)據(jù)。

以求解f(10)作為例子來分析遞歸求解的過程。要求得f(10)，需要求得f(9)和f(8)。同樣，要求得f(9)，要先求得f(8)和f(7)……用樹形結(jié)構(gòu)來表示這種依賴關(guān)系：

圖1 遞歸求解的樹形結(jié)構(gòu)

不難發(fā)現(xiàn)在這棵樹中有很多結(jié)點會重復的，而且重復的結(jié)點數(shù)會隨著n的增大而急劇增加。這意味著計算量會隨著n的增大而急劇增大。用遞歸方法計算的時間復雜度是以n的指數(shù)的方式遞增的。

CPU為i52.5GHZ，8G內(nèi)存，windows764位操作系統(tǒng)，使用System.nanoTime()來計算消耗時間，一輪計算十次取平均耗時，三輪的平均耗時如下（后續(xù)方法相同，不再贅述）：

表1 直接遞歸實現(xiàn)在不同計算值下的執(zhí)行時間

當計算f(80)時，超過8小時未計算出結(jié)果。

3 自底向上實現(xiàn)

上述直接遞歸算法，為了求解f(n)，需要同時遞歸求解f(n-1)和f(n-2)，顯然這樣就做了大量的重復工作。采用自底向上的算法即可避免這樣的冗余。從最小需計算的f(3)開始，逐步向上計算f(4)、f(5)等，將每步計算結(jié)果都保存下來，作為下次計算的初始值，要計算f(n)，則依次計算f(0)，f(1)，f(2)...f(n)，這時計算f(n)只需要利用前兩個結(jié)果即可，這樣算法效率提高到了O(n)。

圖1 自底向上實現(xiàn)示意圖

3.1 動態(tài)數(shù)組

Arraylist能動態(tài)地增加和減少元素，使用它可以保存每次計算的結(jié)果，但是它每次執(zhí)行add等添加元素的方法，都會檢查內(nèi)部數(shù)組的容量是否不夠了，如果是，它會以當前容量的兩倍來重新構(gòu)建一個數(shù)組，將舊元素copy到新數(shù)組，然后丟棄舊數(shù)組。因此效率不如數(shù)組，其核心代碼如下：

3.2 數(shù)組實現(xiàn)

與Arraylist類似，不過是將每次的計算結(jié)果保存到數(shù)組結(jié)構(gòu)中，不再贅述。

3.3 swap實現(xiàn)

注意到以上兩種方式緩存空間僅用于兩次計算，因此可以使用新計算結(jié)果覆蓋原有空間，節(jié)省空間。

圖2 swap實現(xiàn)示意圖

其核心算法如下：

自底向上算法各實現(xiàn)方式的消耗時間對比情況如表2。

表2 自底向上實現(xiàn)在不同計算值下的執(zhí)行時間

對比簡單遞歸實現(xiàn)，計算時間減少了不少，而且隨著計算值增大，節(jié)約時間越明顯。

同時也可以看到不同的實現(xiàn)方式耗時不同，時間復雜度與實際執(zhí)行時間并不是絕對成正比關(guān)系。

4 比內(nèi)公式實現(xiàn)

f(n)=f(n-1)+f(n-2)線性遞推數(shù)列的特征方程為：x2=x+1

核心代碼為

代碼復雜度為O(1)，由于double類型的精度還不夠，所以程序算出來的結(jié)果會有誤差。

5 矩陣乘法實現(xiàn)

斐波那契數(shù)列的表達式可以寫成如下兩個形式：

可以轉(zhuǎn)換為矩陣表達：

因此，成為了矩陣的乘方問題。

若A為n×k矩陣，B為k×m矩陣，則它們的乘積AB(有時記做A·B)將是一個n×m矩陣。前一個矩陣的列數(shù)應該等于后一個矩陣的行數(shù)，得出的矩陣行數(shù)等于前一個矩陣的行數(shù)，列數(shù)等于后一個矩陣的行數(shù)。

其乘積矩陣AB的第i行第j列的元素為：

通過分治法或快速冪，算法效率提高到了O(logn)。所謂分治法就是：

快速冪就是利用結(jié)合律快速計算冪次的方法，應用到矩陣即可：

當n越大，相比較其他算法會節(jié)省更多時間。核心代碼為矩陣乘法與分治法（或快速冪），此處不細述。

表3 比內(nèi)公式和矩陣乘法實現(xiàn)在不同計算值下的執(zhí)行時間

以上使用基本類型long，當n＞92時，會超出long的表達范圍，因此結(jié)果不正確，此時需要用BigInteger解決溢出問題，但會比long耗時多一些。

表4 各算法實現(xiàn)在BigInteger類型下的執(zhí)行時間

可以看到計算值從f(80)到f(800)到f(8000)，10倍的增長，但矩陣法耗時并沒有隨著線性增長，性能最佳。

由于公式法小數(shù)需要使用BigDecimal，效率降低了很多，f(800)結(jié)果達到了10167，公式法精度存在問題，取整后結(jié)果已然不對，保留10000位小數(shù)時僅能保證前13位正確，f(8000)結(jié)果更是達到了101672的數(shù)量級。

6 結(jié)束語

直接使用遞歸算法雖能快速寫出，且容易理解，但其耗費空間和時間都很大，使用自底向上算法可以將時間復雜度降低到O(n)，使用推導出來的公式雖能將時間復雜度降低到O(1)，但冪方運算依然耗時，而且在大數(shù)下無法保證精度。通過升維到二維矩陣計算，可以將時間復雜度降低到O(logn)，在數(shù)據(jù)比較大的情況下，節(jié)省時間比較明顯。

[1] 李亞梅．遞歸算法的分析與應用[J]．中國新通信，2012，14(15)：89-90．

[2] 朱振元，朱承．遞歸算法的非遞歸化實現(xiàn)[J]．小型微型計算機系統(tǒng)，2003(03)：567-570．

[3] 王瑾瑜．斐波那契數(shù)列的幾種解法介紹及優(yōu)缺點分析[J]．科技創(chuàng)新導報，2008(30)：241．

[4] 張新娟．斐波那契數(shù)列通項公式的求法[J]．高等數(shù)學研究，2009，12(04)：56-59．

[5] 彭軍．數(shù)據(jù)結(jié)構(gòu)與算法[M]．北京：人民郵電出版社，2013．

[6] 潘金貴．算法導論[M]．齊德昱編著．北京：清華大學出版社，2003．

Application of Matrix Multiplication in Fibonacci Sequence Calculation

Zhou WeixingChen SiZhang Fan
(China Mobile(Shenzhen)Limited,Shenzhen 518048,Guangdong）

This paper introduces some algorithms of Fibonacci sequence calculation,analyzes the time complexity of recursive,bottom-up and Binet formula algorithms,gives a method to reduce the time complexity by using two dimension matrix multiplication,and compares the execution time of different amount of calculation among these algorithms.It modifies the long data type to BigInteger data type to resolve the data overflow problem,and compares different algorithms’execution time for large number calculation.

Fibonacci;recursive;Binet formula;matrix

TP311.1

A

1008-6609 (2017) 09-0071-03

周衛(wèi)星(1991-)，男，湖南永州人，碩士研究生，軟件開發(fā)工程師，研究方向為J2EE架構(gòu)、圖像識別、計算機網(wǎng)絡(luò)。