矩阵乘法在斐波那契数列计算中的应用

周卫星 陈思 张帆

（中国移动（深圳）有限公司，广东深圳518048）

矩阵乘法在斐波那契数列计算中的应用

周卫星 陈思 张帆

（中国移动（深圳）有限公司，广东深圳518048）

本文介绍了斐波那契数列的一些算法思路，对递归算法、自底向上、比内公式等算法的时间复杂度进行了分析，给出了利用矩阵乘法升维计算降低时间复杂度的方法，对比测试了各算法实现在不同计算量下的执行时间。针对数据溢出，将long数据类型改进为BigInteger的数据类型,给出了大数计算下的执行时间对比。

斐波那契；递归；比内公式；矩阵

1 引言

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。它指的是这样一个数列：1、1、2、3、5、8、13、21、34、……这个数列从第3项开始，每一项都等于前两项之和。在数学上，斐波纳契数列被以递归的方法定义如下：

2 直接递归实现

使用公式f(n)=f(n-1)+f(n-2)，依次递归计算，递归结束条件是f(1)=1，f(2)=1。

核心代码如下：

这种方式可以以非常少的代码实现第N+1项的计算，但是与之相对的，这种算法的代价也非常高，计算机每次调用函数时，为了保证函数执行完毕，都必须将函数调用时的程序现场入栈保存，递归存在大量的自身调用，势必会产生非常庞大的函数现场栈来记录数据。

以求解f(10)作为例子来分析递归求解的过程。要求得f(10)，需要求得f(9)和f(8)。同样，要求得f(9)，要先求得f(8)和f(7)……用树形结构来表示这种依赖关系：

图1 递归求解的树形结构

不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增加。这意味着计算量会随着n的增大而急剧增大。用递归方法计算的时间复杂度是以n的指数的方式递增的。

CPU为i52.5GHZ，8G内存，windows764位操作系统，使用System.nanoTime()来计算消耗时间，一轮计算十次取平均耗时，三轮的平均耗时如下（后续方法相同，不再赘述）：

表1 直接递归实现在不同计算值下的执行时间

当计算f(80)时，超过8小时未计算出结果。

3 自底向上实现

上述直接递归算法，为了求解f(n)，需要同时递归求解f(n-1)和f(n-2)，显然这样就做了大量的重复工作。采用自底向上的算法即可避免这样的冗余。从最小需计算的f(3)开始，逐步向上计算f(4)、f(5)等，将每步计算结果都保存下来，作为下次计算的初始值，要计算f(n)，则依次计算f(0)，f(1)，f(2)...f(n)，这时计算f(n)只需要利用前两个结果即可，这样算法效率提高到了O(n)。

图1 自底向上实现示意图

3.1 动态数组

Arraylist能动态地增加和减少元素，使用它可以保存每次计算的结果，但是它每次执行add等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它会以当前容量的两倍来重新构建一个数组，将旧元素copy到新数组，然后丢弃旧数组。因此效率不如数组，其核心代码如下：

3.2 数组实现

与Arraylist类似，不过是将每次的计算结果保存到数组结构中，不再赘述。

3.3 swap实现

注意到以上两种方式缓存空间仅用于两次计算，因此可以使用新计算结果覆盖原有空间，节省空间。

图2 swap实现示意图

其核心算法如下：

自底向上算法各实现方式的消耗时间对比情况如表2。

表2 自底向上实现在不同计算值下的执行时间

对比简单递归实现，计算时间减少了不少，而且随着计算值增大，节约时间越明显。

同时也可以看到不同的实现方式耗时不同，时间复杂度与实际执行时间并不是绝对成正比关系。

4 比内公式实现

f(n)=f(n-1)+f(n-2)线性递推数列的特征方程为：x2=x+1

核心代码为

代码复杂度为O(1)，由于double类型的精度还不够，所以程序算出来的结果会有误差。

5 矩阵乘法实现

斐波那契数列的表达式可以写成如下两个形式：

可以转换为矩阵表达：

因此，成为了矩阵的乘方问题。

若A为n×k矩阵，B为k×m矩阵，则它们的乘积AB(有时记做A·B)将是一个n×m矩阵。前一个矩阵的列数应该等于后一个矩阵的行数，得出的矩阵行数等于前一个矩阵的行数，列数等于后一个矩阵的行数。

其乘积矩阵AB的第i行第j列的元素为：

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

快速幂就是利用结合律快速计算幂次的方法，应用到矩阵即可：

当n越大，相比较其他算法会节省更多时间。核心代码为矩阵乘法与分治法（或快速幂），此处不细述。

表3 比内公式和矩阵乘法实现在不同计算值下的执行时间

以上使用基本类型long，当n＞92时，会超出long的表达范围，因此结果不正确，此时需要用BigInteger解决溢出问题，但会比long耗时多一些。

表4 各算法实现在BigInteger类型下的执行时间

可以看到计算值从f(80)到f(800)到f(8000)，10倍的增长，但矩阵法耗时并没有随着线性增长，性能最佳。

由于公式法小数需要使用BigDecimal，效率降低了很多，f(800)结果达到了10167，公式法精度存在问题，取整后结果已然不对，保留10000位小数时仅能保证前13位正确，f(8000)结果更是达到了101672的数量级。

6 结束语

直接使用递归算法虽能快速写出，且容易理解，但其耗费空间和时间都很大，使用自底向上算法可以将时间复杂度降低到O(n)，使用推导出来的公式虽能将时间复杂度降低到O(1)，但幂方运算依然耗时，而且在大数下无法保证精度。通过升维到二维矩阵计算，可以将时间复杂度降低到O(logn)，在数据比较大的情况下，节省时间比较明显。

[1] 李亚梅．递归算法的分析与应用[J]．中国新通信，2012，14(15)：89-90．

[2] 朱振元，朱承．递归算法的非递归化实现[J]．小型微型计算机系统，2003(03)：567-570．

[3] 王瑾瑜．斐波那契数列的几种解法介绍及优缺点分析[J]．科技创新导报，2008(30)：241．

[4] 张新娟．斐波那契数列通项公式的求法[J]．高等数学研究，2009，12(04)：56-59．

[5] 彭军．数据结构与算法[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

周卫星(1991-)，男，湖南永州人，硕士研究生，软件开发工程师，研究方向为J2EE架构、图像识别、计算机网络。