剑指Offer 16 数值的整数次方

mario 2020年09月14日 78次浏览

前言

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

分析题目

image.png
最容易想到的当然是直接遍历n,计算x1x2...xn,时间复杂度是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项,因此需做判断。函数需要执行log2N次,所以时间复杂度为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异曲同工。

参考

递归&迭代,快速幂:分治(二分)& 二进制