Implement pow(x, n).
下面介绍一下解决该问题的几种方法以及要注意的地方:
1)最直观容易想到的方法就是用递归方法求n个x的乘积,注意考虑n的正负号,时间复杂度为O(n)
class Solution {
public:
double myPow(double x, int n) {
if(n==)
return 1.0;
if(n<)
return 1.0/pow(x,-n);
return x*pow(x,n-);
}
};
2)考虑到n个x相乘式子的对称关系,可以对上述方法进行改进,从而得到一种时间复杂度为O(logn)的方法,递归关系可以表示为pow(x,n) = pow(x,n/2)*pow(x,n-n/2)
class Solution {
public:
double myPow(double x, int n) {
if(n==)
return 1.0;
if(n<)
return 1.0/pow(x,-n);
double half = pow(x,n>>);
if(n%==)
return half*half;
else
return half*half*x;
}
};