描述

这是一篇适合初级coder的题解。共用三种方法解决。
知识点:数学,递归,快速幂
难度:二星


题解

预处理:求pow(b, n),如果n为负数怎么解决?

假如求图片说明 ,是不是可以转换成图片说明
于是,预处理代码如下:

double Power(double b, int n) {
    if (n < 0) {
        b = 1 / b;
        n = -n;
     }
}

方法一:暴力方法

很显然就是n个b相乘。循环n次。

class Solution {
public:
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double ret = 1.0;
        for (int i=0; i<n; ++i) ret *= b;
        return ret;
    }
};

时间复杂度:O(n)
空间复杂度:O(1)

方法二:递归法(快速幂)

假设我们求图片说明 ,如果我们知道图片说明 ,那么图片说明 ,所以图片说明

但是还有个小问题,如果n是偶数,那么上述没问题。

如果n是奇数,图片说明 , 比如图片说明
代码如下:

class Solution {
public:
    double q_power(double b, int n) {
        if (n == 0) return 1.0;
        double ret = q_power(b, n/2);
        if (n&1) { // 奇数
            return ret * ret * b;
        }
        else {
            return ret * ret;
        }
    }
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        return q_power(b, n);
    }
};

时间复杂度:O(logn),每次规模减少一半
空间复杂度:O(logn),递归栈,因为要记住logn个变量

方法三:非递归的快速幂

假设求图片说明 ,已知6可以表示成二进制110
可以表示成图片说明 ,所以图片说明 可以表示成图片说明 所以,对于二进制数,遇到位数是1的就乘到答案中。
代码如下:

class Solution {
public:

    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double x = b; // 记录x^0, x^1, x^2 ...
        double ret = 1.0;
        while (n) {
            if (n&1) {
                ret *= x; // 二进制位数是1的,乘进答案。
            }
            x *= x;
            n >>= 1;
        }
        return ret;
    }
};

上述方法相当于遍历n的二进制位,是1就乘进结果
时间复杂度:O(logn),因为n的二进制位个数为logn
空间复杂度:O(1)

拓展

STL标准库中,pow函数的代码如下:

template <class T,class Integer, class MonoidOperation>
T power_this(T x, Integer n, MonoidOperation op){ // 可以看成求pow(x, n)
    if (n == 0)
        return identity_element(op); // 可以看成 1
    else{
        while ((n & 1) == 0){
            n >>= 1;
            x = op(x, x); //op看成乘法
        }
        T result = x; // 遇到 二进制中从低位到高位的第一个 1
        n >>= 1;
        while (n != 0){
            x = op(x, x);
            if ((n & 1) != 0)
                result = op(result, x);
            n >>= 1;
        }
        return result;
    }
}

做法跟我们方法三是一样的。