快速幂算法

发布于 2019-12-21  187 次阅读


剑指Offer里和leetcode里都有,剑指offer题目是数值的整数次方,leetcode的题目号是50。

还有一道题也需要快速幂,但是是只取后三位,可能会给一个超级大的指数,这个时候运算其实每次只用后三位去运算,这个题如果不用快速幂和对每次简化的结果进行%1000,保留最后三位的运算,碰到指数大时,必然会指数爆炸,数值溢出。

下面参考自百度百科的概念,指数爆炸的概念:即指数函数的“爆炸性”增长(blow up),
f(x)=a^x (a为常数,如图中a=2 x为指数) 随着x单位长度的递增,f(x)会呈“爆炸性”增长 ,如图

题目为:求A^B的最后三位数的整数,代码在最下方

普通的幂依次乘效率是很低的O(n),使用快速幂算法时间复杂度为 O(log2(n)),指数会不断/2。

1.普通算法,遍历乘N次,注意指数负数的话乘的是1/base
2.快速幂算法
(1)当b为偶数时,a^b可以转为a^2的b/2次方。
(2)当b为奇数时,a^b可以转为a^2的b/2次方,再乘以a。

举个例子:


//没简化的
3^10=3*3*3*3*3*3*3*3*3*3

//两两相乘 也就是

3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)

//简化一下
3^10=(3*3)^5

//然后看运算是不是简单很多,指数10缩减为5了
3^10=9^5

//前面的情况是指数为偶数,这时候指数为5,就是指数为奇数的情况了,我们还是先将其拆开

3^10 = 9*9*9*9*9

//再两两括起来,看是不是多出一个9,所以公式那奇数a^b可以转为a^2的b/2次方,再乘以a,这个乘以a就是为了补上这个末尾的9

3^10=(9*9)*(9*9)*9

//继续简化

3^10 = 81^2*9

3^10=6561^1*9

再简化的话指数就为1/2 = 0了,while也退出循环,最后结果就是6561*9

代码如下

//快速幂    
public double FastPower(double base, int exponent) {
        double result = 1;
        while (exponent != 0) {
            if (exponent % 2 == 1) {
                result *= base;
            } else if (exponent % 2 == -1) {
                result *= (1 / base);
            }
            exponent = exponent / 2;
            base = base * base;
        }
        return result;
    }
//普通方法
public double Power(double base, int exponent) {
        double result = 1;
        while (exponent != 0) {
            if (exponent > 0) {
                result *= base;
                exponent--;
            } else if (exponent < 0) {
                result *= (1 / base);
                exponent++;
            }
        }
        return result;
}
//快速幂 求最后三位, 指数不为负数
//思路不过是在每次*=累计结果时,都只保留最后三位,
//如果不这样而是对最后结果%1000,碰到指数大时必然会数值溢出,指数爆炸
public double FastPower(double base, int exponent) {
        double result = 1;
        while (exponent != 0) {
            if (exponent % 2 == 1) {
                result = (result*base) % 1000;
            }  
            exponent = exponent / 2;
            base = (base * base) % 1000;
        }
        return result;
    }



LoneKing