50.Pow(x,n)
由于直接计算,会出现溢出的情况,因此使用了快速幂算法
这样每次递归都会使得指数减少一半,递归的层数为O(logn)
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;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}