剑指Offer 16 数值的整数次方

前言

这是道中等题，相对简单题，确实多了一点弯弯绕绕。查询时间复杂度的算法时，见有人用数字的整数次方举例子，遂用二分思想做出来。

分析题目

最容易想到的当然是直接遍历n，计算x¹x²...xⁿ，时间复杂度是O(N)

解法1 - 二分法递归

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? myPowHelper(x, n) : 1 / myPowHelper(x, n);
    }

    public double myPowHelper(double x, int n) {
        if (n == 0) return 1;
        double tmp = myPowHelper(x, n / 2);
        if (n % 2 != 0) {
            return tmp * tmp * x;
        }
        return tmp * tmp;
    }
}

每次n折半，显然当n为奇数时会漏掉(n/2)+1项，因此需做判断。函数需要执行log₂N次，所以时间复杂度为O(LogN)。

解法2 - 二分法迭代

class Solution {
    public double myPow(double x, int n) {
        return myPowHelper2(x, n);
    }
    public double myPowHelper2(double x, int n) {
        double result = 1.0;
        for (int i = n; i != 0; i /= 2, x *= x) {
            if (i % 2 != 0) {
                //i是奇数时，需要多乘一个x
                result *= x;
            }
        }
        return n < 0 ? 1.0 / result : result;
    }
}

评论区的非递归解法，与解法1异曲同工。

参考

递归&迭代，快速幂：分治（二分）& 二进制