寒光博客

快速幂运算( 未填坑 矩阵快速幂求解斐波那契数列 )
按常理的算法是复杂度为O(n)如果再降低便是O(nlgn) O(n) static int pow(int...
扫描右侧二维码阅读全文
29
2019/07

快速幂运算( 未填坑 矩阵快速幂求解斐波那契数列 )

按常理的算法是复杂度为O(n)如果再降低便是O(nlgn)

O(n)

    static int pow(int a, int n) {
        int res = 1;
        for (int i = 0; i < n; i++) {
            res *= a;
        }
        return res;
    }

O(nlgn)

  /**
     * 以最快速度求a的n次方
     * O(lgn)
     */
    public static int ex(int a, int n) {
        if (n == 0) return 1;
        if (n == 1) return a;
        int temp = a; //a 的 1 次方
        int res = 1;
        int exponent = 1;
        while ((exponent << 1) < n) {
            temp = temp * temp;
            exponent = exponent << 1;
        }

        res *= ex(a, n - exponent);
        return res * temp;
    }

二进制巧算

    /**
     * m=1010
     */
    public static long ex2(long n, long m) {
        if (n == 0) return 1;
        long pingFangShu = n; //n 的 1 次方
        long result = 1;
        while (m != 0) {
            //遇1累乘现在的幂
            if ((m & 1) == 1)
                result *= pingFangShu;
            //每移位一次,幂累乘方一次
            pingFangShu = pingFangShu * pingFangShu;
            //右移一位
            m >>= 1;
        }
        return result;
    }

GitHub
斐波那契与矩阵的快速幂的结合

本文作者:Author:     文章标题:快速幂运算( 未填坑 矩阵快速幂求解斐波那契数列 )
本文地址:https://dxoca.cn/Algorithm/200.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 11:17 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment