算法分析:很显然用递归。但是直接用递归会造成栈溢出,时间复杂度是o(n)。所以要用分治思想,时间复杂度是o(logN)。
public class Power {
//栈溢出,时间复杂度是o(n)
public double myPow(double x, int n)
{
if(n < 0)
{
return 1/myPow(x, -n);
}
else if(n == 0)
{
return 1;
}
else
{
return x*myPow(x, n - 1);
}
}
//分治思想,时间复杂度是o(logN)
public double myPow2(double x, int n)
{
if(n < 0)
{
return 1/power(x, -n);
}
else
{
return power(x, n);
}
}
public double power(double x, int n)
{
if(n == 0)
{
return 1;
}
double temp = power(x, n/2);
if(n%2 == 0)
{
return temp*temp;
}
else
{
return x*temp*temp;
}
}
}