算法导论-求(Fibonacci)斐波那契数列算法对比

内容

1、斐波那契数列（Fibonacci）介绍

Fibonacci数列应该也算是耳熟能详，它的递归定义如上图所示。

下面2-6分别说明求取Fibonacci数列的4种方法

2、朴素递归算法（Naive recursive algorithm）

在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉，看到题目就能写出如下的递归求解的代码

1  unsigned long long Fibonacci_naive_reu(int n)//朴素递归算法
2 {
3     int result[2] = {0,1};
4     if (n<2)       //退出条件
5        return result[n];
6 
7     return (Fibonacci_naive_reu(n-1)+ Fibonacci_naive_reu(n-2));//递归调用
8 }

其实这种想法很好，但该算法运行时间令人无法忍受，当计算n=50时,用时1200多秒

分析：该算法的时间复杂度T(n)=Θ(∂ⁿ),其中，∂ = (1 + 5^½) / 2，即黄金分割比率。可知，∂>1,随着n增加，时间指数快速增加，所以，平时很少采用！

3、朴素递归平方算法（Naive recursive squaring）

这个算法主要根据斐波那契数列的一条数学性质而来。该性质表明，斐波那契数列F(n)即为φ^n / 5^½向下取整。这样，问题的求解于是变成了一个求x的n次方的问题，在之前的文章里有讲解，链接请进。所以算法的效率为Θ(lgn)。但是这个方法是不太靠谱的，主要是当n比较大时，由于硬件的限制计算机中的浮点运算得到的结果与真实值就产生误差了。实用价值也不大，只能用做理论分析。

4 、自底向上算法（Bottom-up）

考虑到2中的简单递归算法，为了求解F(n)，需要同时递归求解F(n - 1)和F(n - 2)，显然这样就做了大量的重复工作。采用自底向上的算法即可避免这样的冗余。要计算F(n)，则依次计算F0，F1，F2。。。Fn，这时计算Fn只需要利用前两个结果即可，这样算法效率提高到了Θ(n)。n=50时，小于1毫秒。实用价值高。

算法代码：

 1  /************************************************************************/
 2  /*                         自底向上算法                                         */
 3  //  时间复杂度T(n)=o(n)
 4  /************************************************************************/
 5 unsigned long long Fibonacci_bottom_up(int n)//自底向上算法
 6 {
 7     int result[2] = {0, 1};
 8     if(n < 2)
 9         return result[n];
10 
11     unsigned long long  fibNMinusN_1 = 1;
12     unsigned long long  fibNMinusN_2 = 0;
13     unsigned long long  fibN = 0;
14     for(int i = 2; i <= n; ++ i)   //从底到上逐次计算出数列值
15     {
16         fibN = fibNMinusN_1 + fibNMinusN_2;
17 
18         fibNMinusN_2 = fibNMinusN_1;
19         fibNMinusN_1 = fibN;
20     }
21 
22     return fibN;//返回数组值
23 }

5、递归平方算法（Recursive squaring）

上面的算法已经能达到Θ(n)线性效率，然而下面的这个算法能使效率达到T(n) = Θ(lgn)。该算法是基于一个定理，定理以及证明过程如下图所示。这样，问题的求解即成为了矩阵的乘方问题，算法效率于是提高到了Θ(lgn)。

矩阵求幂方法同常数求幂方法，采用分治思想，可参见常数求幂方法，下面是矩阵求幂实现代码：

 1 /************************************************************************/
 2 /*  下面矩阵的n次幂，结果保存在      Result[2][2]                   */
 3 //   矩阵的n次幂，采用分治法，与x的n 次方算法一致，时间复杂度T(n)=o(logn)
 4 //    1    1
 5 //    1    0
 6 /************************************************************************/
 7 void Matrix_power(int n,unsigned long long Result[2][2])//求矩阵幂
 8 {
 9     unsigned long long AResult[2][2];
10     unsigned long long zResult1[2][2];
11     unsigned long long zResult2[2][2];
12 
13     AResult[0][0]=1;AResult[0][1]=1;AResult[1][0]=1;AResult[1][1]=0;
14     if (1==n)
15     {
16         Result[0][0]=1;Result[0][1]=1;Result[1][0]=1;Result[1][1]=0;
17     }
18     else if (n%2==0)
19     {
20         Matrix_power(n/2,zResult1);
21         MUL(zResult1,zResult1,Result);
22     }
23     else if (n%2 == 1)
24     {
25         Matrix_power((n-1)/2,zResult1);
26         MUL(zResult1,zResult1,zResult2);
27         MUL(zResult2,AResult,Result);
28     }
29 }

其中，两个矩阵相乘代码实现如下：

 1 /************************************************************************/
 2 /* 两个 矩阵相乘  、结果矩阵保存在 MatrixResult[2][2]中       */
 3 /************************************************************************/
 4 void MUL( unsigned long long MatrixA[2][2],unsigned long long MatrixB[2][2], unsigned long long MatrixResult[2][2] )//矩阵相乘
 5 {
 6     for (int i=0;i<2 ;i++)
 7     {
 8         for (int j=0;j<2 ;j++)
 9         {
10             MatrixResult[i][j]=0;
11             for (int k=0;k<2 ;k++)
12             {
13                 MatrixResult[i][j]=MatrixResult[i][j]+MatrixA[i][k]*MatrixB[k][j];
14             }
15         }
16     }
17 }

6、完整代码（c++）

Fibonacci.h 其中递归平方法（矩阵求幂法）有两种实现，一种是我自己编码实现，另外是网上copy的代码。

  1 #ifndef FIBONACCI_HH
  2 #define FIBONACCI_HH
  3 struct Matrix2By2
  4 {
  5     Matrix2By2
  6         (
  7         unsigned long long m00 = 0, 
  8         unsigned long long m01 = 0, 
  9         unsigned long long m10 = 0, 
 10         unsigned long long m11 = 0
 11         )
 12         :m_00(m00), m_01(m01), m_10(m10), m_11(m11) 
 13     {
 14     }
 15 
 16     unsigned long long m_00;
 17     unsigned long long m_01;
 18     unsigned long long m_10;
 19     unsigned long long m_11;
 20 };
 21 class Fibonacci
 22 {
 23 public:
 24     unsigned long long Fibonacci_naive_reu(int n);//朴素递归算法
 25     unsigned long long Fibonacci_bottom_up(int n);//自底向上算法
 26     unsigned long long Fibonacci_recur_squar(int n);//递归平方算法
 27     void MUL( unsigned long long MatrixA[2][2],unsigned long long MatrixB[2][2], unsigned long long MatrixResult[2][2] );
 28     void  Matrix_power(int n,unsigned long long result[2][2]);
 29 
 30     Matrix2By2 MatrixMultiply(const Matrix2By2& matrix1, const Matrix2By2& matrix2);
 31     Matrix2By2 MatrixPower(unsigned int n);
 32     unsigned long long Fibonacci_Solution3(unsigned int n);
 33 
 34 };
 35 
 36  unsigned long long Fibonacci::Fibonacci_naive_reu(int n)//朴素递归算法
 37 {
 38     int result[2] = {0,1};
 39     if (n<2)       //退出条件
 40        return result[n];
 41 
 42     return (Fibonacci_naive_reu(n-1)+ Fibonacci_naive_reu(n-2));//递归调用
 43 }
 44  /************************************************************************/
 45  /*                         自底向上算法                                         */
 46  //  时间复杂度T(n)=o(n)
 47  /************************************************************************/
 48 unsigned long long Fibonacci::Fibonacci_bottom_up(int n)//自底向上算法
 49 {
 50     int result[2] = {0, 1};
 51     if(n < 2)
 52         return result[n];
 53 
 54     unsigned long long  fibNMinusN_1 = 1;
 55     unsigned long long  fibNMinusN_2 = 0;
 56     unsigned long long  fibN = 0;
 57     for(int i = 2; i <= n; ++ i)   //从底到上逐次计算出数列值
 58     {
 59         fibN = fibNMinusN_1 + fibNMinusN_2;
 60 
 61         fibNMinusN_2 = fibNMinusN_1;
 62         fibNMinusN_1 = fibN;
 63     }
 64 
 65     return fibN;//返回数组值
 66 }
 67 /************************************************************************/
 68 /* 两个 矩阵相乘  、结果矩阵保存在 MatrixResult[2][2]中       */
 69 /************************************************************************/
 70 void Fibonacci::MUL( unsigned long long MatrixA[2][2],unsigned long long MatrixB[2][2], unsigned long long MatrixResult[2][2] )//矩阵相乘
 71 {
 72     for (int i=0;i<2 ;i++)
 73     {
 74         for (int j=0;j<2 ;j++)
 75         {
 76             MatrixResult[i][j]=0;
 77             for (int k=0;k<2 ;k++)
 78             {
 79                 MatrixResult[i][j]=MatrixResult[i][j]+MatrixA[i][k]*MatrixB[k][j];
 80             }
 81         }
 82     }
 83 }
 84 /************************************************************************/
 85 /*  下面矩阵的n次幂，结果保存在      Result[2][2]                   */
 86 //   矩阵的n次幂，采用分治法，与x的n 次方算法一致，时间复杂度T(n)=o(logn)
 87 //    1    1
 88 //    1    0
 89 /************************************************************************/
 90 void Fibonacci::Matrix_power(int n,unsigned long long Result[2][2])//求矩阵幂
 91 {
 92     unsigned long long AResult[2][2];
 93     unsigned long long zResult1[2][2];
 94     unsigned long long zResult2[2][2];
 95 
 96     AResult[0][0]=1;AResult[0][1]=1;AResult[1][0]=1;AResult[1][1]=0;
 97     if (1==n)
 98     {
 99         Result[0][0]=1;Result[0][1]=1;Result[1][0]=1;Result[1][1]=0;
100     }
101     else if (n%2==0)
102     {
103         Matrix_power(n/2,zResult1);
104         MUL(zResult1,zResult1,Result);
105     }
106     else if (n%2 == 1)
107     {
108         Matrix_power((n-1)/2,zResult1);
109         MUL(zResult1,zResult1,zResult2);
110         MUL(zResult2,AResult,Result);
111     }
112 }
113 unsigned long long Fibonacci::Fibonacci_recur_squar(int n)//递归平方算法
114 {
115     unsigned long long fib_result[2][2];
116     int result[2] = {0, 1};
117     if(n < 2)
118         return result[n];
119     Matrix_power(n,fib_result);
120     return fib_result[0][1];
121 }
122 
123 
124 
125 /************************************************************************/
126 /*     下面是网上copy的递归平方算法的代码                          */
127 /************************************************************************/
128 ///////////////////////////////////////////////////////////////////////
129 // Multiply two matrices
130 // Input: matrix1 - the first matrix
131 //        matrix2 - the second matrix
132 //Output: the production of two matrices
133 ///////////////////////////////////////////////////////////////////////
134 Matrix2By2 Fibonacci::MatrixMultiply
135     (
136     const Matrix2By2& matrix1, 
137     const Matrix2By2& matrix2
138     )
139 {
140     return Matrix2By2(
141         matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
142         matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
143         matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
144         matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
145 }
146 
147 ///////////////////////////////////////////////////////////////////////
148 // The nth power of matrix 
149 // 1  1
150 // 1  0
151 ///////////////////////////////////////////////////////////////////////
152 Matrix2By2 Fibonacci::MatrixPower(unsigned int n)
153 {
154     Matrix2By2 matrix;
155     if(n == 1)
156     {
157         matrix = Matrix2By2(1, 1, 1, 0);
158     }
159     else if(n % 2 == 0)
160     {
161         matrix = MatrixPower(n / 2);
162         matrix = MatrixMultiply(matrix, matrix);
163     }
164     else if(n % 2 == 1)
165     {
166         matrix = MatrixPower((n - 1) / 2);
167         matrix = MatrixMultiply(matrix, matrix);
168         matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
169     }
170 
171     return matrix;
172 }
173 ///////////////////////////////////////////////////////////////////////
174 // Calculate the nth item of Fibonacci Series using devide and conquer
175 ///////////////////////////////////////////////////////////////////////
176 unsigned long long Fibonacci::Fibonacci_Solution3(unsigned int n)
177 {
178     int result[2] = {0, 1};
179     if(n < 2)
180         return result[n];
181 
182     Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
183     return PowerNMinus2.m_00;
184 }
185 #endif

Fibonacci.h

Fibonacci.cpp (主函数)

 1 #include <iostream>
 2 #include <vector>
 3 #include <ctime>
 4 using namespace std;
 5 #include "Fibonacci.h"
 6 
 7 
 8 int main()
 9 {
10     Fibonacci fib;
11     clock_t startTime_For_Fibonacci_naive_reu ;
12     clock_t endTime_For_Fibonacci_naive_reu ;
13     clock_t startTime_For_Fibonacci_bottom_up ;
14     clock_t endTime_For_Fibonacci_bottom_up ;
15     clock_t startTime_For_Fibonacci_recur_squar1 ;
16     clock_t endTime_For_Fibonacci_recur_squar1 ;
17     clock_t startTime_For_Fibonacci_recur_squar2 ;
18     clock_t endTime_For_Fibonacci_recur_squar2 ;
19 
20     startTime_For_Fibonacci_naive_reu=clock();
21     cout<<fib.Fibonacci_naive_reu(40)<<endl;//朴素递归算法
22     endTime_For_Fibonacci_naive_reu=clock();
23 
24     startTime_For_Fibonacci_bottom_up=clock();
25     cout<<fib.Fibonacci_bottom_up(40)<<endl;//自底向上算法
26     endTime_For_Fibonacci_bottom_up=clock();
27 
28     startTime_For_Fibonacci_recur_squar1=clock();
29     cout<<fib.Fibonacci_recur_squar(40)<<endl;//我自己编写的递归平方算法
30     endTime_For_Fibonacci_recur_squar1=clock();
31 
32     startTime_For_Fibonacci_recur_squar2=clock();
33     cout<<fib.Fibonacci_Solution3(40)<<endl;//网上copy的递归平方算法
34     endTime_For_Fibonacci_recur_squar2=clock();
35 
36     cout<<"朴素递归算法用时： "<<(endTime_For_Fibonacci_naive_reu-startTime_For_Fibonacci_naive_reu)/(1.0*CLOCKS_PER_SEC)<<"秒"<<endl;
37     cout<<"自底向上算法用时： "<<(endTime_For_Fibonacci_bottom_up-startTime_For_Fibonacci_bottom_up)/(1.0*CLOCKS_PER_SEC)<<"秒"<<endl;
38     cout<<"我自己编写的递归平方算法用时： "<<(endTime_For_Fibonacci_recur_squar1-startTime_For_Fibonacci_recur_squar1)/(1.0*CLOCKS_PER_SEC)<<"秒"<<endl;
39     cout<<"网上copy的递归平方算法用时： "<<(endTime_For_Fibonacci_recur_squar2-startTime_For_Fibonacci_recur_squar2)/(1.0*CLOCKS_PER_SEC)<<"秒"<<endl;
40     system("Pause");
41     return 0;
42 }

输出：

结：朴素递归算法用时太多，实用价值不大，自底向上算法效率为线性，较高，平时用较多，递归平方算法效率为对数级，且编程可实现，实用价值很大。并且经过测试，当n值变很大后，递归平方算法效率明显高于自底向上算法效率。

7、参考资料

【1】http://zhedahht.blog.163.com/blog/static/25411174200722991933440/

【2】http://blog.csdn.net/xyd0512/article/details/8220506

算法导论-求(Fibonacci)斐波那契数列算法对比

目录

1、斐波那契数列（Fibonacci）介绍

2、朴素递归算法（Naive recursive algorithm）

3、朴素递归平方算法（Naive recursive squaring）

4 、自底向上算法（Bottom-up）

5、 递归平方算法（Recursive squaring）

6、完整代码（c++）

7、参考资料

内容

1、斐波那契数列（Fibonacci）介绍

2、朴素递归算法（Naive recursive algorithm）

3、朴素递归平方算法（Naive recursive squaring）

4 、自底向上算法（Bottom-up）

5、 递归平方算法（Recursive squaring）

其中，两个矩阵相乘代码实现如下：

6、完整代码（c++）

7、参考资料

5、递归平方算法（Recursive squaring）

5、递归平方算法（Recursive squaring）