斐波那契数列 logn 实现

对于fibonacci：

logn主要是基于计算一个数的n次方的方法。

计算一个数的n次方的方法：

递归方式计算乘方，logn级别.

code:

public static int involution(int a, int n){
        if(n == 0) return 1;
        if(n <= 1 ) return a;//这里不考虑n小于0
        int temp = involution(a,n>>1);//计算a的n/2次方,这里为整除,为奇数时和(n-1)/2结果一致
        return n & 1 == 0 ? temp * temp : temp * temp * a;//
    }

fib原理：

可以使用数学归纳法证明，自己证！

使用前面介绍的方法简化计算矩阵的n次方，最终为logn级别！

code:

public class Fibonacci{
    public static int[][] matrixMul(int[][] a,boolean flag){//flag为true计算a的平方，flag为false计算a*init
        int[][] b = {{a[0][0],a[0][1]},{a[1][0],a[1][1]}};//a的拷贝
        if(flag){//a和a自身相乘
            a[0][0] = b[0][0]*b[0][0] + b[0][1]*b[1][0];
            a[0][1] = b[0][0]*b[0][1] + b[0][1]*b[1][1];
            a[1][0] = b[1][0]*b[0][0] + b[1][1]*b[1][0];
            a[1][1] = b[1][0]*b[0][1] + b[1][1]*b[1][1];
        }else{//a和init相乘
            a[0][0] = b[0][0] + b[0][1];
            a[0][1] = b[0][0];
            a[1][0] = b[1][0] + b[1][1];
            a[1][1] = b[1][0];
        }
        return a;
    }
    public static int[][] fibonacci(int[][] a,int n){
        if( n <= 1 ){//这里不考虑0和负数
            return a;
        }
        int[][] matXmat = matrixMul(fibonacci(a,n>>1),true);//计算a的n/2次方再做平方运算，
        return n & 1 == 0 ? matXmat : matrixMul(matXmat,false);//n为偶数时直接返回，n为奇数时，需要再乘上init矩阵
    }
    public static void main(String[] args){
        int[][] init = {{1,1},{1,0}};
        int[][] fib = fibonacci(init,5);//不考虑异常用例和0项
        System.out.println("斐波那契第6项："+fib[0][0]);//从1计数 1 1 2 3 5 8
    }
}