由斐波那契数列引述到矩阵快速幂技巧

求斐波那契数列矩阵乘法的方法

1）斐波那契数列的线性求解（O(N)）的方式非常好理解

2)同时利用线性代数，也可以改写出另一种表示：

|F(N),F(N-1)| = |F(2),F(1)| * 某个二阶矩阵的N-2次方

3)求出这个二阶矩阵，进而最快求出这个二阶矩阵的N-2次方

斐波那契数列的线性求解

public static int f1(int n){
        if(n<1){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        return f1(n-1)+f1(n-2);
    }

    public static int f2(int n){
        if(n<1){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        int pre=1;
        int res=1;
        int tmp=0;
        for(int i=3; i<=n; i++){
            tmp=res;
            res+=pre;
            pre=tmp;
        }
        return res;
    }

斐波那契数列的矩阵乘法求解

上述求解方式时间复杂度是O(N)，但是可以优化到O(LogN)。

斐波那契数列的递归公式：F(n)=F(n-1)+F(n-2)。这个递归公式没有条件转移，是个严格的递推式，所以可以优化到O(LogN)。

所以，接下来我们通过线性代数证明|F(N),F(N-1)| = |F(2),F(1)| * 某个二阶矩阵的N-2次方（线性代数就是为了解决严格递推第几项的问题而发明的）

新的问题：一个矩阵的n次方如何算得足够快？

先解决：一个数的n次方如何算得足够快。（本质是利用二分，关键是利用二进制）

10^75
=10^(64+8+2+1)
=10^(1001011)

所以一个矩阵的n次方也是这样算。

package com.harrison.class15;

/**
 * @author Harrison
 * @create 2022-03-27-18:37
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code01_FibonacciProblem {
    public static int f1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }

    public static int f2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int pre = 1;
        int res = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res += pre;
            pre = tmp;
        }
        return res;
    }

    public static int f3(int n){
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int[][] base={
                {1,1},
                {1,0}
                };
        int[][] res=matrixPower(base,n-2);
        // |F(N),F(N-1)| = |F(2),F(1)| * 某个二阶矩阵的N-2次方
        return res[0][0]+res[1][0];
    }

    // p：次方数
    public static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        // 单位矩阵的概念：右对角线全是1，其余位置全是0
        // 一个单位矩阵 * a矩阵 = a矩阵
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        // res=矩阵中的1
        int[][] t = m;// 矩阵1次方
        // 有1就要乘上去，乘完就右移扔掉
        for (; p != 0; p >>= 1) {
            // (次方数 & 1) !=0 说明最末尾有1
            if ((p & 1) != 0) {
                res=muliMatrix(res,t);
            }
            t=muliMatrix(t,t);
        }
        return res;
    }

    /*
    两个矩阵乘完之后的结果返回，矩阵相乘得到的是一个新的矩阵
    新矩阵的第一行第一列的结果是由第一个矩阵的第一行分别与第二个矩阵的第一列相乘的和
     */
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        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;
    }

    public static void main(String[] args) {
        int n = 19;
        System.out.println(f1(n));
        System.out.println(f2(n));
        System.out.println(f3(n));
        System.out.println("===");
    }
}

最终推广的结论！！！