【算法】多方法求斐波那契函数

关于斐波那契函数

斐波那契函数$F(N)$是由斐波那契数列得到，该数列从$0$和$1$开始，之后的每一项都由前两项相加得到，即有

$F(0)=0, F(1)=1$ $F(N)=F(N-1)+F(N-2)$

对斐波那契函数求值，就是给定一个N值，返回$F(N)$的值。

递归法

检查N的值，如果N <= 1，则将N的值返回。
若N > 1，则通过调用$N=F(N-1)+F(N-2)$来递归，最终返回N的值。

C++代码实现如下：

int fib(int N) {
    if(N <= 1) return N;
    N = fib(N - 1) + fib(N - 2); //递归过程
    
    return N;
}

时间复杂度：$O(2^n)$.

这是计算斐波那契函数最慢的一种方法，但其实现起来比较方便，也更容易想到。
空间复杂度：$O(n)$.

为了跟踪fib函数的调用，我们需要与N成正比的空间大小。

自下而上迭代

若N <= 1，返回N的值。
迭代至N，将各个计算得到的值存在一个数组里。
每次迭代用数组当前位置的前两个数得到当前的数。
返回数组中的第N个值。

C++代码实现如下：

int fib(int N) {
    if(N <= 1) return N;
    vector<int> res;
    res.push_back(0);
    res.push_back(1); //先将0和1存入数组
    for(int i = 2; i < N; i++) {
        res.push_back(res[i - 1] + res[i - 2]); //当前位置的值由前两个数相加得到
    }
    
    return res[N - 1];
}

时间复杂度：$O(n)$

迭代了N次。
空间复杂度：$O(n)$

使用了大小为N的数组。

求幂矩阵

我们知道，斐波那契数列矩阵方程为：

$\left[ \begin{matrix} f(n)\\ f(n-1) \end{matrix} \right] = \left[ \begin{matrix} 1&1\\ 1&0 \end{matrix} \right] \left[ \begin{matrix} f(n-1)\\ f(n-2) \end{matrix} \right] = {\left[ \begin{matrix} 1&1\\ 1&0 \end{matrix} \right]}^{n-1} \left[ \begin{matrix} f(1)\\ f(0) \end{matrix} \right]$

通过矩阵求幂即可得到$F(N)$的值。

若N <= 1，返回N的值。
计算{[1, 1], [1, 0]}的N - 1次方得到的矩阵。
由于该矩阵乘以{[1], [0]}后，第一个元素就是$F(N)$的值，所以返回。

C++代码实现如下：

int fib(int N) {
    if(N <= 1) return N;
    vector<vector<int>> A = {{1, 1}, {1, 0}};
    recursiveMatrix(A, N - 1); //求幂
    
    return A[0][0]；
}

void mutip(vector<vector<int>>& A, vector<vector<int>>& B) {
    int a = A[0][0] * B[0][0] + A[0][1] * B[1][0];
    int b = A[0][0] * B[0][1] + A[0][1] * B[1][1];
    int c = A[1][0] * B[0][0] + A[1][1] * B[1][0];
    int d = A[1][0] * B[0][1] + A[1][1] * B[1][1];
    //矩阵相乘的实现
    A[0][0] = a;
    A[0][1] = b;
    A[1][0] = c;
    A[1][1] = d;
}

void recursiveMatrix(vector<vector<int>>& A, int N) {
    if(N <= 1) return;
    recursiveMatrix(A, N/2);
    mutip(A, A); 
    //二分求幂，A即为求幂之后的矩阵
    vector<vector<int>> B = {{1, 1}, {1, 0}}; //由于A的值会变化，B用于存储源矩阵
    if(N % 2 != 0) {
        mutip(A, B);
    }
}

时间复杂度：$O(logN)$.
空间复杂度：$O(logN)$.

黄金分割比

Binet公式求斐波那契数列的第$n$项时用到了黄金分割比$\varphi$。

$a_n=\frac{1}{\sqrt{5}}[{(\frac{1+\sqrt{5}}{2})}^n-{(\frac{1-\sqrt{5}}{2})}^n]$

直接使用Binet公式计算$F(N)$的值。

C++代码实现如下：

int fib(int N) {
    double g = (1 + sqrt(5)) / 2;
    double h = (1 - sqrt(5)) / 2;
    return 1 / sqrt(5) * (pow(g, N) - pow(h, N));
}

时间复杂度：$O(1)$.

没有使用任何迭代或者递归。
空间复杂度：$O(1)$.

参考

【1】Leetcode斐波那契数.