斐波纳契数列实现及优化

1.递归实现

class Solution {
public:
    /*
     * @param n: an integer
     * @return: an ineger f(n)
     */
    int fibonacci(int n) {
        if(1 == n) {
            return 0;
        }else if(2 == n) {
            return 1;
        } else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
};

总耗时: 2946 ms
91% 数据通过测试.

2.非递归实现

问题分析：在递归实现中，由于大量的重复运算导致速度慢，所以采用非递归形式，思路也非常简单：从 f(0) 开始根据公式叠加至 f(n) 。

class Solution {
public:
    /*
     * @param n: an integer
     * @return: an ineger f(n)
     */
    int fibonacci(int n) {
        if(1 == n) {
            return 0;
        }else if(2 == n) {
            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;
        }
    }
};

总耗时: 247 ms
100% 数据通过测试.

结果分析

• 结果：经测试 C++ 最快可以以 10ms 轻松通过 LintCode 的评测。
• 分析：时间复杂度为 o(n) ，空间复杂度为 o(1) ，效果不错。
• 细节：使用 while 代替 for 节省了一个 Int(4Byte) 的空间。

3.递归实现优化

问题分析：类似的递归重复计算问题很多，但未必都可以简单的像 斐波那契数列 问题这么容易化为非递归，那么有没有办法递归的前提下保证没有重复计算呢？思路也很简单：计算结果加入缓存。

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;
    }
};

总耗时: 198 ms
100% 数据通过测试.

结果分析

• 分析：虽然空间复杂度相对非递归提升到了 o(n) ，不过在不改动递归结构的前提下，也算达到了不错的效果。

• 细节：

  1.在枚举 f(1) 、 f(2) 后再声明变量，以节约内存空间。
  2.n 是从 1 开始，buffer 是从 0 开始。
  3.f(1) 和 f(2) 要一开始加进来，如果递归加入会顺序相反，导致结果出错。

4.矩阵快速幂实现
待续...