题目描述

实现 pow(x, n)，即计算 $x$ 的 $n$ 次幂函数。

样例

输入：2.00000, 10
输出：1024.00000

输入：2.10000, 3
输出：9.26100

输入：2.00000, -2
输出：0.25000

说明

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。

算法

(快速幂) $O(\log n)$

1. 按照定义，计算 $x$ 的 $n$ 次方是将 $n$ 个 $x$ 连乘，效率比较低，会超时。
2. 因为乘法具有结合律，考虑每次将一部分连乘批量计算好，作为最终答案的一部分。
3. 这就可以将 $n$ 进行二进制拆分，若 $n$ 的二进制位的第 $k$ 位是 $1$，则 $ans$ 可以乘上 $x^{2^k}$。
4. 而计算 $x^{2^k}$，只需每次将自身做平方即可。

时间复杂度

• 由于只进行 $O(\log n)$ 次乘法操作，故时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    #define LL long long
    double myPow(double x, int n) {
        double ans = 1, p = x;
        LL t = abs((LL)(n)); // 注意 n 为 INT_MIN时，abs 会爆掉 int。
        for (; t; t >>= 1) { // 将 n 进行二进制拆分。
            if (t & 1)
                ans = ans * p; // p 是提前计算好的批量连乘。
            p = p * p; // 每次更新 p，自身平方。
        }
        return n > 0 ? ans : 1 / ans;
    }
};