斐波那契数列的对数时间复杂度计算分析（说服你对数时间复杂度是可以算的）+求平方的对数时间分析

斐波那契数列的对数时间复杂度计算分析（说服你对数时间复杂度是可以算的）+求平方的对数时间分析

我先强调一下

请侧重注意时间复杂度，不要在意语句的作用

先上一下斐波那契的代码（解释在注释里面）

跟语言没关系，都差不多啦，大家想看别的语言的解释

没学过Java也能看，只是它在第一个，我就直接复制了（真的）

力扣

先上只看时间复杂度的句子

class Solution {
    static final int MOD = 1000000007;
    
    
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[][] q = {{1, 1}, {1, 0}};

        int[][] res = pow(q, n - 1);//pow的时间复杂度为对数级，pow函数里面的注释解释了
//        到这里应该清楚对数级是可以算的了吧
        return res[0][0];
    }


//    pow时间复杂度为lgn级别
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
//            大于等于1也可以
            if ((n & 1) == 1) {
//                注意mutiply里面没有递归
                ret = multiply(ret, a);//multiply时间复杂度：常数级别，可以自己分析一下
            }
            n >>= 1;//相当于整除以2，这里是关键哦！！！！！
//            就是以前的练习题哦，大家应该会
//            算这个只看while的时间复杂度，控制循环次数应该就是这一句
//            这个是你想要的解释吗？？
            a = multiply(a, a);
        }
        return ret;
    }




    //自己先分析一下
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //我就强调一下，要不可能被忽略
    public int[][] multiply(int[][] a, int[][] b) {

        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++)
            {
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
            }
        }
        return c;
    }
}



public class hello {
    public static void main(String[] args) {
        int n = 8;
        n = n&1;
        System.out.println(n);
//        Solution s = new Solution();
//        System.out.print(s.fib(2));
    }
}

上一遍有一些解释语句，不单单只解释复杂度

class Solution {
    static final int MOD = 1000000007;//然后取模用的数字

    //想法是0，1，1，2，3，5那么n就是下标
    //注意n是下标
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[][] q = {{1, 1}, {1, 0}};
//        1，0分别是第2项，和第1项
//        1,1分别是第3项，和第2项
//        继续写
//        2，1分别是第4项，和第3项

//        pow函数的定义在下面
        int[][] res = pow(q, n - 1);//pow的时间复杂度为对数级，pow函数里面的注释解释了
//        到这里应该清楚对数级是可以算的了吧
        return res[0][0];
    }


//    pow时间复杂度为lgn级别
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
//            或者大于等于1
            
//            n & 1 这是位计算
//            结果等于0，n就是偶数
//            1，n就是奇数
            if ((n & 1) == 1) {
//                mutiply的定义在下面
//                注意mutiply里面没有递归
                ret = multiply(ret, a);//multiply时间复杂度：常数级别，可以自己分析一下
            }
//            以13>>1为例，首先将13转换为二进制形式1101，
//            然后右移1位，最低位丢弃，最高位使用符号位0补充，
//            得110，转换为十进制数为6，相当于13/2
            
            n >>= 1;//相当于整除以2，这里是关键哦！！！！！
//            就是以前的练习题哦，大家应该会
//            算这个只看while的时间复杂度，控制循环次数应该就是这一句
//            这个是你想要的解释吗？？
            

//            mutiply的定义在下面
            a = multiply(a, a);
        }
        return ret;
    }

    
    //用到矩阵的知识了
    //没学过的就先不用理解mutiply的作用了
    //但你一定清楚mutiply的时间复杂度吧
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //时间复杂度：常数级别
    //我就强调一下，要不可能被忽略
    public int[][] multiply(int[][] a, int[][] b) {

        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++)
            {
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
            }
        }
        return c;
    }
}


//如果你的想法是0，1，1，2，3，5那么n就是下标
//是1，1，2，3，5那么n是位序

public class hello {
    public static void main(String[] args) {
        int n = 8;
        n = n&1;
        System.out.println(n);
//        Solution s = new Solution();
//        System.out.print(s.fib(2));
    }
}

求平方

有异曲同工之妙

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
//这一句请分析分析，看看是不是和while很像
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

怎么样，是不是看完了，又不知道之前自己为什么不懂了，哈哈，拿笔算一算就好啦