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

Question

我看到人们实施时pow(x,n),他们总是使用下面的类似解决方案.我的困惑是,下面的解决方案比较强力多倍x 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

这种技术通过平方正式称为指数化.它通过重复乘法比"平坦"取幂需要更少的操作,因此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;
}

演示.