Java 递归幂方法使递归更有效

Question

我想改变这个幂法(n 是指数(：

public static double exponentiate(double x, int n) {
counter++; 
if (n == 0) {
return 1.0;
} else if (n == 1) {
return x;
} else {
return x * exponentiate(x, n - 1);
}
}

我想更改方法以使其更有效，因此该方法不是打开 n 次，而是在不使用类 MATH 的情况下打开最大 (n/2+1( 次。

到目前为止，我想出了这个代码：

public static double exponentiate(double x, int n) {
counter++; 
if (n == 0) {
return 1.0;
} else if (n == 1) {
return x;
} else {
if (n % 2 == 0) {
n = n-(n-1);
} else {
n = ((n-1) / 2) + n;
}
return ((x * x) * exponentiate(x, n - (n / 2)));
}
}

但不知何故，它只适用于奇数 n，甚至不适用于 n。

有人可以帮忙吗？

谢谢！

Answer 1

我认为您可以通过计算一次exponentiate(x,n/2)并使用它来优化上述方法以运行O(logn)。

像这样的东西：-

public static double exponentiate(double x, int n) 
{ 
int temp; 
if(n == 0) 
return 1; 
temp = exponentiate(x, n/2); 
if (n%2 == 0) 
return temp*temp; 
else
return x*temp*temp; 
} 

希望这有帮助！

Answer 2

我不知道这是否是您搜索的解决方案，但这是在 O(log(n(( 时间内执行幂运算的算法示例

public static double exponentiate(double x, int n) {
if (n == 0) {
return 1.0;
} else if (n == 1) {
return x;
} else {
return ((n % 2 == 0) ? 1 : x) * exponentiate(x * x, n  / 2);
}
}