优化幂运算

最近在刷OJ时候发现了一个问题，那就是计算X^62，这是一个很简单的问题，也很容易实现。这个问题有一个很容易的实现方案就是时间复杂度为logN的算法，就是计算62次X相乘。

代码如下##

    public static BigInteger pow(int x, int n) {

        BigInteger result = BigInteger.ONE; // 初始化result为1

        // BigeInteger的multiply方法需要BigInteger类型
        BigInteger param = BigInteger.valueOf(x);

        for (int i = 0; i < n; i++) {
            result = result.multiply(param);
        }

        return result;
    }

代码很简单，但是如果是计算x^10000，甚至更多呢？虽然程序倾向如去做繁琐重复的事情， 但是显然如果有效率更好的算法，何乐而不为呢？

分析##

对于幂运算，是一个重复乘以常数的问题。如果将这个问题拆解，那么任何一个部分都是相似的，那么显然，就可以用递归来解决这个问题。关于递归的问题可以参考我的另外一篇文章递归的基本法则。

思路##

对于递归，首先需要找到基本情形，当N=1时，result=X；其次就是每一次递归都要朝基本情形进行推进，对于此问题N=62而言，则可以按照如下方式拆解：

X^62 = X^31 * X^31, X^31 = (X^15 * X^15) * X, X^15 = (X^7 * X^7) * X,
X^7 = (X^3 * X^3) * X, X^3 = (x * x) *x.

以此类推,向基本类型推进X=1推进。

代码##

    public static BigInteger betterPow(BigInteger x, int n) {

        if (n == 0) {
            return 1;  
        }

        if (n % 2 == 0) {
            return betterPow(x.pow(2), n / 2);  
        } else {
            return betterPow(x.pow(2), n / 2).multiply(x);  
        }
    }

为了更好的理解上述代码，现在以betterPow(3,3)为例，分析代码执行过程：
首先是第一次执行，betterPow(3,3) 等价于betterPow(9,1)*3。现在的问题就变成了计算betterPow(9,1)，betterPow(9,1)等价于betterPow(81,0)*9。现在的问题就变成了计算betterPow(81,0)，而当n=0时是基本情形，所以betterPow(81,0)等于1。

所以最终计算公式为
betterPow(3,3)=betterPow(9,3)*3=betterPow(8,1)*9*3=1*9*3=27

可以看出，第一种解决方案用了62次乘法来计算X^62，而优化后的方案则用了9次乘法运算。并且优化后的方案最多需要的乘法次数为2logN，远小于N。其复杂度为O（logN）。