数据结构与算法(四)：斐波那契数列

相关文献：
数据结构与算法(一)：基础理论
数据结构与算法(二)：线性表的实现
数据结构与算法(三)：线性表算法设计练习
数据结构与算法(四)：斐波那契数列
数据结构与算法(五)：LRU
数据结构与算法(六)：栈
数据结构与算法(七)：栈/队列的算法解题思想
数据结构与算法(八)：队列
数据结构与算法(九)：二叉树/线索化二叉树
数据结构与算法(十)：哈夫曼树

题目

假设⼀对兔⼦每年⽣⼀对孩⼦，兔宝宝在两年之后才能⻓⼤，才能有⾃⼰的孩⼦，且兔⼦永远不会死。那么N年后会有多少只兔⼦？

斐波那契算法

F(1) -> 1
F(2) -> 1
F(3) -> 2
F(4) -> 3
F(5) -> 5
F(6) -> 8
F(7) -> 13
F(8) -> 21
...
F(n) = F(n-1) + F(n-2)
第N年后兔子的数量 = 第N-1年的数量 + 第N-2年的数量
即前两数的和

一、递归算法

什么时候使用递归？

• a.数学定义是递归的
• b.数据的结构是递归的
• c.问题的解法是递归的

/**
 递归
 时间复杂度：O(2^n)。
 */
int fib(int n) {
 if (n <= 2) return 1; // 叶子节点
 else return fib(n-1) + fib(n-2); // 枝节点
}

分析算法
这个算法需要多⻓时间？这个算法需要多⻓性能？以执⾏的指令为标准

分析出规律：

• 叶子节点：在二叉树中没有子节点，即F(1)和F(2) 相当于代码中的 return 1;
• 枝节点：在二叉树中有子节点，相当于代码中的return fib(n-1) + fib(n-2);
• F(n)的叶子节点数量等于F(n)的结果值（最终都以F(1)/F(2)返回1）；
• F(n)的枝节点数量等于F(n)底下的叶子节点数量-1；

得出：执⾏n次 = F(n) + 2F(n) - 2 即 3F(n) - 2

为什么会这么慢？
原因在于不断地⼀遍⼜⼀遍地重复计算已经知道答案的节点结果值。

二、动态规划 Dynamic Program

/**
 动态规划 DP
 时间复杂度：O(n)。
 空间复杂度：O(n)。
 */
int fib2(int n) {
    int f[n+1];
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    return f[n];
}

把之前计算的结果，把它保存下来。

• 弊端：需要去分析程序使⽤的内存量。⼀个程序虽然花费了很多时间，但是仍然可以运⾏它，只是需要等待更⻓的时间。
  但是，如果⼀个程序占⽤⼤量内存，可能根本⽆法运⾏它。

需要降低空间复杂度:

/**
 动态规划 DP
 时间复杂度：O(n)。
 空间复杂度：O(1)。
 */
int fib3(int n){
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

此时空间复杂度已经优化成O(1)，但是时间复杂度还是O(n)。
有没有一种可能去优化时间复杂度呢？通过矩阵

三、矩阵法

1.矩阵（matrix）定义

2.用矩阵法分析斐波那契

// 声明一个2X2的矩阵
struct Matrix {
    int mat[2][2];
};

// 实现矩阵相乘
struct Matrix matrixMultiply(struct Matrix* a, struct Matrix* b) {
    struct Matrix c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.mat[i][j] = (*a).mat[i][0] * (*b).mat[0][j] + (*a).mat[i][1] * (*b).mat[1][j];
        }
    }
    return c;
}

// 实现斐波那契矩阵的n次方
void matpow(int n, struct Matrix *m) {
    struct Matrix q;
    // q: {{1,1},{1,0}}
    q.mat[0][0] = q.mat[0][1] = q.mat[1][0] = 1;
    q.mat[1][1] = 0;
    for (int i = 0; i < n; i++)
        *m = matrixMultiply(m, &q);
}

1.矩阵法1

实现上面的理论：

/**
 矩阵
 时间复杂度：O(n)。
 空间复杂度：O(1)。
 */
int fib4(int n) {
    if (n < 2) { return n; }
    struct Matrix ret; // 单位矩阵（任何矩阵乘以它，都等于本身）{{1,0},{0,1}}
    ret.mat[0][0] = ret.mat[1][1] = 1;
    ret.mat[0][1] = ret.mat[1][0] = 0;
    matpow(n-1, &ret); // 矩阵q的n-1次方，得到第一个元素就是结果
    return ret.mat[0][0];
}

2.矩阵法2

对于矩阵法1的时间复杂度的优化：

我们可以把矩阵看成是基数2，那么结果可以简化看成是2的n次方；
比如n=9的情况 就可以写成 (2的4次方)再平方再乘以2 即(16的平方)*2。

为什么要这样呢？我们先计算出n/2的次方的结果，就不需要计算另一半的相同的运算啦。从而达到节约计算的时间。

这里的2就代表着矩阵{{1,1},{1,0}}

这种方式的话，就可以保存之前已经计算好的结果，就不需要重复计算。

void matpow2(int n, struct Matrix *m) {
    if (n > 1) {
        matpow(n/2, m); // 先计算出一半次方的结果
        *m = matrixMultiply(m, m); // 再平方
    }
    if (n & 1) {
        // 判断最后一位如果是奇数的话
        // 再需要乘以一个{{1,1}, {1,0}}
        struct Matrix q;
        q.mat[0][0] = q.mat[0][1] = q.mat[1][0] = 1;
        q.mat[1][1] = 0;
        *m = matrixMultiply(m, &q);;
    }
}

/**
 矩阵
 时间复杂度：O(logn)。
 空间复杂度：O(1)。
 */
int fib5(int n) {
    struct Matrix ret;
    ret.mat[0][0] = ret.mat[1][1] = 1;
    ret.mat[0][1] = ret.mat[1][0] = 0;
    matpow2(n-1, &ret);
    return ret.mat[0][0];
}

再继续优化，就是第四部分内容。

四、通项公式

斐波那契是有一个通项公式的：

/**
 通项公式
 时间复杂度：O(1)。
 */
int fib6(int n) {
    double sqrt5 = sqrt(5);
    double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
    return round(fibN / sqrt5);
}

学习算法的总结：

• 先分析，分析啥？想啥就分析啥
• 先按⾃⼰能理解的去实现
• 观察，优化，再分析
• 能⼒范围之内实现的有哪些？
• 能⼒范围之外还有哪些好⽅式？学习，记录
• 实际应⽤？结合具体场景分析
• 并不⼀定最优秀的算法就是最合适的