浮点数的整数次方

1.暴力算法：

这种算法效率不高

class Solution {
public:
         double Power(double base, int exponent) {
             if(exponent==0) return 1;
             if(base==0) return 0;
             double ans=1.0;
             if(exponent>0){
                 while(exponent>0){
                     ans*=base;
                     exponent--;
                 }
                 return ans;
             }else{
                 exponent=-exponent;
                 while(exponent>0){
                     ans*=base;
                     exponent--;
                 }
                 ans=1.0/ans;//注意这里除的时候要用1.0
                 return ans;
             }
         }
};

2.递归快速幂算法

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个变量

3.非递归快速幂算法

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)