Pow(x, n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000示例 2：
输入：x = 2.10000, n = 3
输出：9.26100示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25「快速幂算法」的本质是分治算法。举个例子，如果我们要计算
x^{64}
，我们可以按照：
x \to x^2 \to x^4 \to x^8 \to x^{16} \to x^{32} \to x^{64}
的顺序，从
x
开始，每次直接把上一次的结果进行平方，计算
6
次就可以得到
x^{64}
的值，而不需要对
x
乘
63
次
x
。
再举一个例子，如果我们要计算
x^{77}
，我们可以按照：
x \to x^2 \to x^4 \to x^9 \to x^{19} \to x^{38} \to x^{77}
的顺序，在
x \to x^2
，
x^2 \to x^4
，
x^{19} \to x^{38}
这些步骤中，我们直接把上一次的结果进行平方，而在
x^4 \to x^9
，
x^9 \to x^{19}
，
x^{38} \to x^{77}
这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个
x
。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘
x
。但如果我们从右往左看，分治的思想就十分明显了：
当我们要计算
x^n
时，我们可以先递归地计算出
y = x^{\lfloor n/2 \rfloor}
，其中
\lfloor a \rfloor
表示对
a
进行下取整；
根据递归计算的结果，如果
n
为偶数，那么
x^n = y^2
；如果
n
为奇数，那么
x^n = y^2 \times x
；
递归的边界为
n = 0
，任意数的
0
次方均为
1
。
由于每次递归都会使得指数减少一半，因此递归的层数为
O(\log n)
，算法可以在很快的时间内得到结果。
class Solution {
public:
double quickMul(double x, long long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
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)
，即为递归的层数。这是由于递归的函数调用会使用栈空间。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读