斐波那契数列源自于对生物界中无限繁殖问题的思考。意大利数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)在他的名著《算法之书》中提出的一个问题:
假设兔子可以无限繁殖下去，小兔子需要2个月的成长期，成熟后每对兔子每个月能生育一对新的小兔子。那么从一对小兔子开始，兔子的数量是如何变化的？
第1个月：1
第2个月：1
第3个月：2（1对成熟兔子，1对新生兔子）
第4个月：3（1对成熟兔子，1对1个月的兔子，1对新生兔子）
第5个月：5（2对成熟兔子，1对1个月的兔子，2对新生兔子）
.....
兔子的数量就是著名的菲波那切数列:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,…
如果用正式的数学公式定义就是
如果把定义域扩展到整数域上，也可以有如下等价定义：
根据这个公式定义，我们可以使用递归方式迅速实现这个算法：
int fibonacci(int n) {
if (n == 1) {
return 1;
}
if (n >= 2) {
return fibonacci(n - 1) + fibonacci(n - 2);
}
return 0;
}
上面这个递归实现简洁而直观，但是算法复杂度却是指数级的。主要问题是大量的重复计算。例如计算第10项，需要计算第8项和第9项，但是在计算第9项的过程中又需要计算第8项。如果我们能够将计算的结果缓存起来，避免重复计算，我们可以得到一个线性复杂度的实现：
int fibonacci(int n) {
if (n <= 0) {
return 0;
}
int x = 0;
int y = 1;
int i = 0;
while (i < n) {
x = x + y;
y = x + y;
i += 2;
}
return i == n ? y : x;
}
如果将斐波那契数列看做是一个一维空间的点，那么线性复杂度基本已经是我们能想到的算法极限。但是如果我们将思考的维度提升到二维空间，我们看看会发生什么。首先我们引入矩阵乘法：
用矩阵乘法重新定义斐波那契数列如下：
化简得到：
已知矩阵的快速幂算法是对数级O(logn)的，所以斐波那契数列通过矩阵乘法也就有了对数级的算法。事实上，不仅仅是斐波那契数列，所有第N项可以表示为前N-1项的线性多项式的，都可以通过矩阵乘法获得对数级的算法。
例如我们定义如下数列：
转换为矩阵乘法的形式就是：
在斐波那契数列这个问题的思考上，我们如果将数列思考为零维空间的点，我们得到了一个指数级的算法；我们如果将数列思考为一维空间的点，我们得到了一个线性级的算法；我们如果将数列思考为二维空间的点，我们得到了一个对数级的算法。思考的维度，有的时候就决定了我们思考问题的极限。
网友评论