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);
    }
}

我想更改方法以使其更有效，因此在不使用 class MATH 的情况下，该方法不会打开 n 次，而是最多 (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

我不知道这是否是您搜索的解决方案，但这是在 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);
    }
}

Answer 2

我认为你可以通过计算一次 exponentiate(x,n/2) 并使用它来将上述方法优化为运行 for 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; 
}

希望对您有所帮助！

Java 递归取幂方法使递归更高效

Java recursion exponentiation method making recursion more efficient

java

methods

recursion

exponentiation

coding-efficiency