题目描述
实现Pow(x，n)，即计算x的n次幂函数（即，x^n）。
示例
- 示例1
输入：x = 2.00000, n = 10
输出：1024.00000 - 示例2
输入：x = 2.10000, n = 3
输出：9.26100 - 示例3
输入：x = 2.00000, n = -2
输出：0.25000
方法思路
快速幂+递归
举个例子：我们要计算x^64，我们可以按照：
image.png
的顺序计算6次，就可以得到最终的结果。
再举一个例子：如果我们要计算x^77，我们可以按照：
image.png
的顺序，在最后一步之前我们得到x^76，只需要再将结果乘一个x就可以得到最终的结果。
class Solution {
public double myPow(double x, int n) {
long N = n;
return N>0?quickMul(x,N) : 1.0/quickMul(x,-N);
}
public 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)，即为递归的层数。这是由于递归的函数调用会使用栈空间。
网友评论