斐波那契数列的实现及优化

  |   分类   |   热度 ℃

前言

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++

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
10
11
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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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)$ 应有的优势，不过根据其单步计算量提升，时间却与 非递归 递归优化 达到同一水平，可以判断出其效果还是有的。

总结

理论上讲的通的道理只是理论上，小问题到了手上解决掉才能明白。简单的问题弄透也不容易，我记录一下这个思路省得忘了，能够有人用得上自然更好。当然谁要是能给我个更好的答案才是极好的。


本文链接：斐波那契数列的实现及优化
版权声明：本文章采用CC BY-NC-SA 3.0 CN许可协议进行许可。转载请注明出处！