实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
1
2
| 输入: 2.00000, 10
输出: 1024.00000
|
示例 2:
1
2
| 输入: 2.10000, 3
输出: 9.26100
|
示例 3:
1
2
3
| 输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
|
说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
采用快速幂等法。有递归和迭代两个版本。
递归版本
快速幂算法的本质是分治算法。例如在计算 x^64 时我们可以看作求 x^32 的平方，进而可以看作求 x^16 的四次方……
再来看一般情况如果需要求 x^77 ，可以看作 x^38 * x^38 *x，对 x^38 可以看作 x^19 的平方，x^19 可以看作 x^9 * x^9 * x……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
double quickMul(double x, long N){
if(N == 0) return 1.0;
double y = quickMul(x, N/2);
return N % 2 == 0 ? y * y : y * y * x;
}
}
|
时间复杂度 O(logN)，空间复杂度 O(logN)。
迭代版本
以 x^77 为例，首先看 77 这个整数，77化为二进制得到1001101，我们可以将 77 表示为 64+8+4+1。我们只需算出 x 的 2 的指数倍次方的结果就可以表示 x 的所有次方。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
double quickMul(double x, long N){
double ans = 1.0;
double x_contribute = x;
while(N != 0){
if( (N & 1) == 1 ){
ans *= x_contribute;
}
x_contribute *= x_contribute;
N = N >>> 1;
}
return ans;
}
}
|
时间复杂度 O(logN)，空间复杂度 O(1)。
迭代法真是妙蛙种子吃着妙脆角妙进了米奇妙妙屋，妙到家了。