快速幂

快速幂

快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高（为O(指数n)），就是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

double fastPower(double base,int power){
    if(power == 0) return 1;
    if(power < 0){
        base = 1 / base;
        power = -power;
    }
    double res = 1;
    while(power>0){
        if(power % 2 == 0){
            // 如果指数为偶数
            power = power / 2; // 把指数缩小为一半
            base = base * base;// 把底数变为原来的平方
        }else{
            // 如果指数为奇数
            power = power - 1;// 把指数减去1,使其变成一个偶数
            result = result * base; //把指数为奇数时分离出来的底数的一次幂计算上
            power = power / 2; // 此时指数为偶数，可以继续执行偶数时的操作
            base = base * base;
        }
        
    }
}

优化写法

double fastPower(double base,int power){
    if(power == 0) return 1;
    if(power < 0){
        base = 1 / base;
        power = -power;
    }
    double result = 1;
    while(power>0){
        if(power % 2 == 1){
            // 如果指数为奇数
            result = result * base; //把指数为奇数时分离出来的底数的一次幂计算上
        }
        power = power / 2;
        base = base * base;
    }
    return result;
}

再次优化

double fastPower(double base,int power){
    if(power == 0) return 1;
    if(power < 0){
        base = 1 / base;
        power = -power;
    }
    double result = 1;
    while(power>0){
        // 与运算代替求模
        if((power & 1) == 1){
            // 如果指数为奇数
            result = result * base; //把指数为奇数时分离出来的底数的一次幂计算上
        }
        // 右移代替除法
        power = power >> 1;
        base = base * base;
    }
    return result;
}

————————————————
版权声明：本文为CSDN博主「刘扬俊」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_19782019/article/details/85621386

赏

谢谢你请我吃糖果

微信