java - 递归计算 pow(x, n) 比蛮力更好吗？

Question

我看到人们在实现 pow(x,n) 时，总是使用下面类似的解决方案。我的困惑是，下面的解决方案与 n 次的蛮力倍数相比有什么优势？

public class Solution {
    public double pow(double x, int n) {
        if(n == 0)
            return 1;
        if(n<0){
            n = -n;
            x = 1/x;
        }
        return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
    }
}

Answer 1

这项技术的正式名称为 Exponentiation by squaring .它比通过重复乘法进行的“平坦”幂运算需要更少的操作，因此 N^k 的结果在 log₂k 时间内计算。

请注意，虽然此算法的实现 通常是递归的，但不一定非要这样做。可以用迭代而不是递归重写算法，以产生相同的加速:

public static double pow(double x, int n) {
    if(n == 0)
        return 1;
    double y = 1;
    while (n > 1) {
        if (n%2 == 1) {
            y *= x;
        }
        x *= x;
        n /= 2;
    }
    return x*y;
}

Demo.