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

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

（中國移動(dòng)（深圳）有限公司，廣東深圳518048）

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

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

（中國移動(dòng)（深圳）有限公司，廣東深圳518048）

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

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

1 引言

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

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

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

核心代碼如下：

這種方式可以以非常少的代碼實(shí)現(xiàn)第N+1項(xiàng)的計(jì)算，但是與之相對的，這種算法的代價(jià)也非常高，計(jì)算機(jī)每次調(diào)用函數(shù)時(shí)，為了保證函數(shù)執(zhí)行完畢，都必須將函數(shù)調(diào)用時(shí)的程序現(xiàn)場入棧保存，遞歸存在大量的自身調(diào)用，勢必會(huì)產(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é)點(diǎn)會(huì)重復(fù)的，而且重復(fù)的結(jié)點(diǎn)數(shù)會(huì)隨著n的增大而急劇增加。這意味著計(jì)算量會(huì)隨著n的增大而急劇增大。用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以n的指數(shù)的方式遞增的。

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

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

當(dāng)計(jì)算f(80)時(shí)，超過8小時(shí)未計(jì)算出結(jié)果。

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

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

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

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

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

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

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

3.3 swap實(shí)現(xiàn)

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

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

其核心算法如下：

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

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

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

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

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

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

核心代碼為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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

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

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

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

[6] 潘金貴．算法導(dǎo)論[M]．齊德昱編著．北京：清華大學(xué)出版社，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ā)工程師，研究方向?yàn)镴2EE架構(gòu)、圖像識(shí)別、計(jì)算機(jī)網(wǎng)絡(luò)。