描述

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

题解

预处理：求pow(b, n)，如果n为负数怎么解决？

假如求 ,是不是可以转换成%5E%7B2%7D "图片标题")
于是，预处理代码如下：

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)

方法二：递归法（快速幂）

假设我们求 ，如果我们知道 ，那么%5E%7B2%7D "图片标题") ，所以%5E%7B2%7D "图片标题")

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

如果n是奇数，%5E%7B2%7D%20%20x "图片标题") ， 比如%5E%7B2%7D%20%20x "图片标题")
代码如下：

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;
    }
}

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