斐波那契数列学习

复习过程中涉及到计算算法的时间复杂度，课后例题中的“计算斐波那契数列时间复杂度”引起了自己的思考，通过学习，总结出好集中不同的方式。

斐波那契数列简介

斐波那契数列（意大利语：Successione di Fibonacci），又译为菲波拿契数列、菲波那西数列、斐波那契数列、黄金分割数列。
在数学上，费波那契数列是以递归的方法来定义：

F[0] = 0
F[1] = 0
F[n] = F[n-1] + Fn-2

用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

特别指出：0不是第一项，而是第零项。

计算方法

递归法

递归计算斐波那契数列的JavaScript如下：

function Fibonacci1(n){
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    return Fibonacci1(n-1) + Fibonacci1(n-2);
}

递归的方法很简单，但是显然十分显然存在大量的重复运算，效率低下很低，还会占用大量的内存。

时间复杂度：T(n) = O(2^n)

递推法

为了避免递归的低效率，我们可以采取累加的方式，一项一项的计算，JavaScript代码如下：

function Fibonacci2(n){
    a = 0;
    b = 1;
    if(n==0)
        return a;
    for(i = 1;i <= n;i++){
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

时间复杂度：T(n) = O(n)
空间复杂度：O(n)

公式法

以下是斐波那契数列的常见递推公式：

$$ F_{n}=\dfrac {1}{\sqrt {5}}\times \left[ \left( \dfrac {1+\sqrt {5}}{2}\right) ^{n}-\left( \dfrac {1-\sqrt {5}}{2}\right) ^{n}\right] $$

公式法的JavaScript代码如下：

function Fibonacci3(n){
    root_five = sqrt(5);
    f1=f2=1;
    for(i=1;i<=n;i++){
        f1 *= (1+root_five)/2;
        f2 *= (1-root_five)/2;
    }
    result = (f1 - f2)/root_five;
    return int(result);
}

虽然公式看起来不是很复杂，但是当中有很多的浮点运算，返回的结果也会因为n越来越大而不断产生更大的误差，因此并不可靠。

矩阵法

$$ \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\times f_{n-1}+1\times F_{n}-2 \ 1\times f_{n-1}+0\times F_{n-2} \end{bmatrix}=\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix} $$

由此可推得：

$$ \begin{bmatrix} F_{n} \ F_{n-1} \end{bmatrix}=\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^{n-1}\times \begin{bmatrix} F_{1} \ F_{0} \end{bmatrix}=\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^{n-1}\times \begin{bmatrix} 1 \ 0 \end{bmatrix} $$

那这里就把问题转换为了求矩阵的n-1次幂，利用快速幂的方式来计算：

$$ a_{n}=\begin{cases}a^{\dfrac {n}{2}}a^{\dfrac {n}{2}},ifniseven\ a^{\dfrac {n-1}{2}}a^{\dfrac {n-1}{2}}a,ifnisodd\end{cases} $$

以上方法的JavaScript代码如下：

// 矩阵乘法
function multiMatrix(int[][] m1,int[][] m2) {
//参数判断什么的就不给了，如果矩阵是n*m和m*p,那结果是n*p
    int[][] res = new int[m1.length][m2[0].length];
    for (int i = 0; i < m1.length; i++) {
        for (int j = 0; j < m2[0].length; j++) {
            for (int k = 0; k < m2.length; k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}
// 矩阵快速幂
function Fibonacci4(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1 || n == 2) { 
        return 1;
    }
    //底
    int[][] base = {{1,1},
                    {1,0}};
    //求底为base矩阵的n-2次幂
    int[][] res = matrixPower(base, n - 2);
    //根据[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)，f(n)就是
    //1*res[0][0] + 1*res[1][0]
    return res[0][0] + res[1][0];
}