由于简书不支持
Latex，建议去我的博客看原文：斐波纳契数列实现及优化
求关注、求交流、求意见、求建议。
前言
LintCode 是专注代码面试的在线评测系统，有很多代码题，可以用 Java、C++、Python 在线答题，我觉得还不错，就决定把做一做这些题，然后把题目的实现、优化思路写下来，一来是为了有更深的理解，二来是讨论一下还有没有更好的方法。
题目
LintCode：斐波纳契数列
描述
查找 斐波纳契数列 中第 N 个数。
所谓的 斐波纳契数列 是指：
- 前两个数是
0和1。 - 第
i个数是第i-1个数和第i-2个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
样例
给定 1，返回 0
给定 2，返回 1
给定 10，返回 34
实现
递归实现
问题分析
根据 斐波那契数列 的定义得：
$$
\begin{aligned}
f(1) & = 0\
f(2) & = 1\
f(n) & = f(n - 1) + f(n - 2)\qquad n\in{3,4,5\ldots}
\end{aligned}
$$
根据上述表达式最明显的实现方式便是递归。
实现 - C++
class Solution{
public:
int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
};
实现 - Java
class Solution {
public int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
结果分析
- 结果：结果不尽人意，速度非常慢，甚至没有通过 LintCode 的评测。
- 分析：这种递归不同于一般的递归，在
n较大时，两次递归调用中存在大量的重复运算，导致速度非常慢。
非递归实现
问题分析
在递归实现中，由于大量的重复运算导致速度慢，所以采用非递归形式，思路也非常简单：从 f(0) 开始根据公式叠加至 f(n) 。
实现 - C++
class Solution{
public int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
int n1 = 0;
int n2 = 1;
int sn = 0;
while (n > 2) {
sn = n1 + n2;
n1 = n2;
n2 = sn;
n--;
}
return sn;
}
}
};
实现 - Java
class Solution{
public:
int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
int n1 = 0;
int n2 = 1;
int sn = 0;
while (n > 2) {
sn = n1 + n2;
n1 = n2;
n2 = sn;
n--;
}
return sn;
}
}
};
结果分析
- 结果：经测试
C++最快可以以10ms轻松通过 LintCode 的评测。 - 分析：时间复杂度为
o(n)，空间复杂度为o(1)，效果不错。 - 细节：使用
while代替for节省了一个Int(4Byte)的空间。
递归实现优化
问题分析
类似的递归重复计算问题很多，但未必都可以简单的像 斐波那契数列 问题这么容易化为非递归，那么有没有办法递归的前提下保证没有重复计算呢？思路也很简单：计算结果加入缓存。
实现 - C++
class Solution{
public:
vector<int> buffer;
int fibonacci(int n) {
if(n == 1){
return 0;
} else if (n == 2){
return 1;
}
int n1, n2, sn;
if (buffer.size() == 0) {
buffer.push_back(0);
buffer.push_back(1);
}
if (buffer.size() > n - 2) {
n1 = buffer[n - 2];
} else {
n1 = fibonacci(n - 1);
}
if (buffer.size() > n - 3) {
n2 = buffer[n - 3];
} else {
n2 = fibonacci(n - 2);
}
sn = n1 + n2;
if (buffer.size() < n) {
buffer.push_back(sn);
}
return sn;
}
};
实现 - Java
class Solution {
ArrayList<Integer> buffer = new ArrayList<Integer>();
public int fibonacci(int n) {
if(n == 1){
return 0;
} else if (n == 2){
return 1;
}
int n1, n2, sn;
if (buffer.size() == 0) {
buffer.add(0);
buffer.add(1);
}
if (buffer.size() > n - 2) {
n1 = buffer.get(n - 2);
} else {
n1 = fibonacci(n - 1);
}
if (buffer.size() > n - 3) {
n2 = buffer.get(n - 3);
} else {
n2 = fibonacci(n - 2);
}
sn = n1 + n2;
if (buffer.size() < n) {
buffer.add(sn);
}
return sn;
}
}
结果分析
- 结果：经测试
C++同样最快可以以10ms轻松通过 LintCode 的评测。Java也跑出了1269ms的成绩，可喜可贺。 - 分析：虽然空间复杂度相对非递归提升到了
o(n)，不过在不改动递归结构的前提下，也算达到了不错的效果。 - 细节：
- 在枚举
f(1)、f(2)后再声明变量，以节约内存空间。 -
n是从1开始，buffer是从0开始。 -
f(1)和f(2)要一开始加进来，如果递归加入会顺序相反，导致结果出错。
矩阵快速幂实现
概述
根据@iFzzzh的提醒，发现了大大降低时间复杂度的方法。
原理
先介绍一下什么是快速幂，如下式：
$$
f(n) = a^n\tag{1}
$$
当 $n$ 为偶数时则有:
$$
f(n) = (a{\frac{n}{2}})2=f(\frac{n}{2})^2\tag{2}
$$
当 $n$ 为奇数时则有:
$$
f(n) = (a{\lfloor\frac{n}{2}\rfloor})2 \times a=f(\lfloor\frac{n}{2}\rfloor)^2\times a\tag{3}
$$
显然 (1) 式时间复杂度为 o(n) ，而 (2) (3) 式复杂度为 o(log_2 n)，这就是快速幂，简单的来说就是以二分降幂的方式减少计算步骤。
问题分析
类比上述的快速幂法，采用矩阵的方式也可以将 斐波那契数列 化为 a^n 的格式，达到降幂的效果：
$$
\begin{aligned}
\begin{bmatrix}
f(n)\
f(n-1)\
\end{bmatrix}&=
\begin{bmatrix}
f(n-1)+f(n-2)\
f(n-1)\
\end{bmatrix}\\
&=\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}\times
\begin{bmatrix}
f(n-1)\
f(n-2)\
\end{bmatrix}\\
&=\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}^2\times
\begin{bmatrix}
f(n-2)\
f(n-3)\
\end{bmatrix}\
&\qquad\qquad\quad\vdots\
&=\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}^{n-2}\times
\begin{bmatrix}
f(2)\
f(1)\
\end{bmatrix}\
\end{aligned}
$$
根据 斐波那契数列 的定义，f(1) f(2) 为常数，此时便可以通过快速幂的方式计算 f(n) 的值了。
实现 - C++
class Solution{
public:
int fibonacci(int n) {
if(n == 1){
return 0;
}
if(n == 2){
return 1;
}
int s[2][2];
rxn(n - 2, s);
return s[0][0];
}
void rxn(int n, int result[2][2]){
if(n == 0){
result[0][0] = 1;
result[0][1] = 0;
result[1][0] = 0;
result[1][1] = 1;
return;
}
if(n == 1){
result[0][0] = 1;
result[0][1] = 1;
result[1][0] = 1;
result[1][1] = 0;
return;
}
if(n > 1){
int s[2][2] = {1, 1, 1, 0};
int buffer[2][2];
rxn(n / 2, buffer);
int buffer2[2][2];
mul(buffer, buffer, buffer2);
if(n % 2 == 0){
result[0][0] = buffer2[0][0];
result[0][1] = buffer2[0][1];
result[1][0] = buffer2[1][0];
result[1][1] = buffer2[1][1];
}else{
mul(buffer2, s, result);
}
}
}
void mul(int m1[2][2], int m2[2][2], int result[2][2]) {
result[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
result[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
result[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
result[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
}
};
实现 - Java
class Solution {
public int fibonacci(int n) {
if(n == 1){
return 0;
} else if (n == 2){
return 1;
}
int s[][] = new int[2][2];
rxn(n - 2, s);
return s[0][0];
}
public void rxn(int n, int[][] result){
if(n == 0){
result[0][0] = 1;
result[0][1] = 0;
result[1][0] = 0;
result[1][1] = 1;
return;
}
if(n == 1){
result[0][0] = 1;
result[0][1] = 1;
result[1][0] = 1;
result[1][1] = 0;
return;
}
if(n > 1){
int s[][] = {{1, 1}, {1, 0}};
int buffer[][] = new int[2][2];
rxn(n / 2, buffer);
int buffer2[][] = new int[2][2];
mul(buffer, buffer, buffer2);
if(n % 2 == 0){
result[0][0] = buffer2[0][0];
result[0][1] = buffer2[0][1];
result[1][0] = buffer2[1][0];
result[1][1] = buffer2[1][1];
}else{
mul(buffer2, s, result);
}
}
}
public void mul(int[][] m1, int[][] m2, int[][] result) {
result[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
result[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
result[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
result[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
}
}
结果分析
- 结果：
C++最快可以以10ms通过 LintCode 的评测。Java最快可以以1200ms通过 LintCode 的评测。 - 分析：可能是由于 LintCode 测试数据不够大的原因，矩阵快速幂并没有体现出时间复杂度为
o(log_2 n)应有的优势，不过根据其单步计算量提升，时间却与非递归递归优化达到同一水平，可以判断出其效果还是有的。
总结
理论上讲的通的道理只是理论上，小问题到了手上解决掉才能明白。简单的问题弄透也不容易，我记录一下这个思路省得忘了，能够有人用得上自然更好。当然谁要是能给我个更好的答案才是极好的。
