剑指 Offer 16. 数值的整数次方

题解链接：剑指 Offer 16. 数值的整数次方

方法一：迭代实现快速幂

解题思路

通过迭代的方法，自下向上实现快速幂求解过程，初始化结果 \(res = 1\)，底数 \(t = x\) ，幂次为 \(n\)。当 \(n\) 为奇数时，\(res = res * t\)，先乘上一个 \(t\)，此时还有 \(n-1\) 个 \(t\) 相乘，即相当于计算 \((t * t) ^ {(n - 1) / 2}\)，将问题规模减半，依次循环下去。

代码

class Solution {
public:
    double quickmul(double x, long long N) {
        double res = 1.0, t = x;
        while (N > 0) {
            if (N & 1) res *= t; // N 为奇数时
            t *= t;
            N >>= 1;
        }
        return res;
    }
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickmul(x, N) : 1.0 / quickmul(x, -N);  
    }
};

复杂度分析

时间复杂度：每次底数\(×2\)，即幂次减半（除去幂次为奇数时），最终循环 \(log n\)次，故时间复杂度为 \(O(log n)\)；
空间复杂度：\(O(1)\)。

方法二：递归实现快速幂

解题思路

通过递归方法，自上向下实现快速幂求解过程。当 \(n\) 为奇数时，返回 \(x * x ^ {n - 1}\)；当 \(n\) 为偶数时，返回\(x ^ {n / 2} * x ^ {n / 2}\)；递归边界为 \(n == 0\) 时，返回 \(1\)。

代码

class Solution {
public:
    double quickmul(double x, long long N) {
        if (N == 0) return 1;
        if (N & 1) return x * quickmul(x, N - 1);
        else {
            double y = quickmul(x, N / 2);
            return y * y;
        }
    }
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickmul(x, N) : 1.0 / quickmul(x, -N);  
    }
};

复杂度分析

时间复杂度：\(O(log n)\)；
空间复杂度：\(O(log n)\)。