快速幂算法

幂运算当指数较大时，需要进行很多次乘法操作，时间复杂度较高
使用快速幂算法,可大大降低时间复杂度

基本思路

底数为x，指数为n，定义变量res（初始值为1）保存结果，对指数n进行讨论

  • 若n为偶数，那么x^n == (x^2)^(n/2)，将x自身平方，n减半
  • 若n为奇数，则将当前x的值并入res（即res *= x），同时n自减1
    最终n自减至0，此时res已保存正确的x^n的值

代码实现

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
def quickPwo(x,n):
    res = 1
    if n < 0:   #处理n为负数的情况
        x = 1/x
        n = -n
    while n > 0:
        if n % 2 == 0:
            x *= x
            n /= 2
        else:
            res *= x
            n -= 1
    return res

C++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
double quickPow(double x,int n){
    long long res = 1;
    if(n < 0 ){ //处理n为负数的情况
        x = 1.0/x;
        n = -n;
    }
    while(n > 0){
        if(n % 2 == 0){
            x *= x;
            n /= 2;
        }
        else{
            res *= x;
            n--;
        }
    }
    return res;
}