算法笔记之快速幂

算法笔记之快速幂

问题引入

问题描述:求A^B的最后三位数，并输出。

看到这道题目，最简单的思想就是求幂之后取余，代码如下：

public static long Pow_1(long base,long power){
    long res = 1;
    for(int i=0;i<=power;i++){
        res = res*base;
    }
    return res%1000;
}

以上代码无法解决超大指数的情况，也就是x的增长，pow(base,x)会呈现爆炸性增长。

而且long是64位，所以res在指数很大的情况下会发生溢出。解决方案也很简单，每次结果取余。

public static long Pow_2(long base,long power){
    long res = 1;
    for(int i=0;i<=power;i++){
        res %= 1000;
        res = res*base;
    }
    return res%1000;
}

目前这种方法就可以很好的解决问题了，但是当前的算法时间复杂度是O(n).如果是power的大小时1e9甚至更大，程序的表现并不好。其实，完全有比进行n次乘法更高效的方法。接下来就是快速幂的方法介绍。

快速幂方法

快速幂，顾名思义就是更快速的实现幂的计算。传统计算幂的算法时间复杂度这么高(相对来说），是因为指数为n，就要做n次运算。但是，根据如下推导：

5^10 = (25)^5 = (625)^2*25
正如的例子:如果求n^k,那么当k为偶数时,n^k = (n*n)^(k/2);
		   当k为奇数时，n^k = (n*n)^(k/2)*n;
只要把底数变为原来的平方，指数就缩减为了原来的一半。
那么，我们对底数每次都取平方，那么指数会一直缩减一半，当指数缩小为1，底数就是当前的结果。

代码如下：

public static long Pow_3(long base,long power){
    long res = 1;
    while (power>0){
        if((res&1)==1){
            res = (res*base)%1000;
        }
        power >>= 1;
        base =(base*base)%100;
    }
    return res;
}

实际上，快速幂就是尽可能的复用之前的运算结果，时间复杂度为O(logn).