题目:求斐波那契数列的第n项
写一个函数,输入n,求斐波那契数列的第n项。斐波那契数列的定义如下:
大多数人看到后第一时间都会写出如下代码:
递归:方法直观但时间效率低
long long Fibonacci(unsigned int n)
{
if(n<=0)
return 0;
if(n==1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
即使很多教科书在讲解递归时都会利用该问题,但并不说明递归的解法最适合这道题目,对于这道题递归存在严重的效率问题。
我们以求解f(10)为例来分析递归求解的过程,用树形结构表示如下图所示:
我们可以发现,在这棵树中有很多节点是重复的,且随着n的增大重复的节点数急剧增加,同时计算量也急剧增大,用递归方法计算的时间复杂度是以n的指数的方式递增的。
改进:
尽量避免重复计算,可以将已经得到的数列中间项保存起来,在下次需要计算的时候先查找一下,如果已经计算过了后面就不再重复计算。
最简单的方法即从下往上计算,用f(0)和f(1)计算f(2),以此类推就可以得到第n项,这种思路的时间复杂度为O(n)。
循环:时间效率提高
long long Fibonacci(unsigned n)
{
if(n<2)
return n;
long long fib1=1;
long long fib2=0;
long long fibn=0;
for(unsigned int i=2;i<=n;i++)
{
fibn=fib1+fib2;
fib2=fib1;
fib1=fibn;
}
return fibn;
}
扩展方法:
还存在更快的O(logn)算法,需要用到如下的数学公式:
我们只需要求后面的矩阵就可以得到f(n),现在问题转换为求矩阵的乘方。如果只是简单地从0开始循环,n次方需要n次运算,则其时间复杂度仍然是O(n),并不比前面快。但我们可以考虑乘方的如下性质:
从上面的公式中我们可以看出,若想求得n次方,就要先求得n/2次方,再把n/2次方的结果平方一下即可。可以用递归的思路实现。
基于矩阵乘法:创意算法,但隐含时间常数较大
#include <cassert>
struct Matrix2By2
{
Matrix2By2
(
long long m00 = 0,
long long m01 = 0,
long long m10 = 0,
long long m11 = 0
)
:m_00(m00), m_01(m01), m_10(m10), m_11(m11)
{
}
long long m_00;
long long m_01;
long long m_10;
long long m_11;
};
Matrix2By2 MatrixMultiply
(
const Matrix2By2& matrix1,
const Matrix2By2& matrix2
)
{
return Matrix2By2(
matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}
Matrix2By2 MatrixPower(unsigned int n)
{
assert(n > 0);
Matrix2By2 matrix;
if(n == 1)
{
matrix = Matrix2By2(1, 1, 1, 0);
}
else if(n % 2 == 0)
{
matrix = MatrixPower(n / 2);
matrix = MatrixMultiply(matrix, matrix);
}
else if(n % 2 == 1)
{
matrix = MatrixPower((n - 1) / 2);
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
}
return matrix;
}
long long Fibonacci_Solution3(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
return PowerNMinus2.m_00;
}