题目描述

题目链接

https://leetcode.cn/problems/powx-n/

思路

求最简单的方法是通过循环将个乘起来，依次求，时间复杂度为。我们可以利用「快速幂算法」将时间复杂度降低至，快速幂算法有递归和迭代两个版本。我们先从递归版本开始讲起，再逐步引出迭代的版本。

当指数为负数时，我们可以计算再取倒数得到结果，因此我们只需考虑为自然数的情况。

1. 快速幂 + 递归

「快速幂算法」的本质是分治算法。举个例子，如果我们要计算，我们可以按照： :::success ::: 的顺序，从开始，每次直接把上一次的结果进行平方，计算次就可以得到 的值，而不需要对乘次。

再举一个例子，如果我们要计算，我们可以按照： :::success ::: 的顺序，在，，这些步骤中，我们直接把上一次的结果进行平方，而在，，这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个。

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘。但如果我们从右往左看，分治的思想就十分明显了：

• 当我们要计算时，我们可以先递归地计算出，其中表示对进行下取整；
• 根据递归计算的结果，如果为偶数，那么；如果为奇数，那么；
• 递归的边界为，任意数的次方均为。

由于每次递归都会使得指数减少一半，因此递归的层数为，算法可以在很快时间内得到结果。注意 Java 中的 int 变量，因此当时执行会因越界而赋值出错。我们需要先将存入 long 型变量中再进行后续操作。

public double myPow(double x, int n) {
    long N = n;
    return N < 0 ? 1 / recur(x, -N) : recur(x, N);
}
private double recur(double x, long n) {
    if (n == 0) {
        return 1;
    }
    double y = recur(x, n >> 1);
    return ((n & 1) == 0) ? y * y : y * y * x;
}

• 时间复杂度：，即为递归的层数。
• 空间复杂度：，即为递归的层数。这是由于递归的函数调用会使用栈空间。

  2. 快速幂 + 迭代

  由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘。但我们不妨找一找规律，看看哪些地方额外乘了，并且它们对答案产生了什么影响。

我们还是以作为例子：

并且把需要额外乘的步骤打上了标记。可以发现：

• 中额外乘的在中贡献了；
• 中额外乘的在之后又被平方了次，因此在中贡献了；
• 中额外乘的在之后又被平方了次，因此在中贡献了；
• 最初的在之后被平方了次，因此在中贡献了。

我们把这些贡献相乘，恰好等于。而这些贡献的指数部分又都是的幂次：，这是因为每个额外乘的在之后都会被平方若干次。而这些指数恰好就对应了的二进制表示中的每个！

因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数的二进制拆分为

那么

这样一来，我们从开始不断地进行平方，得到，如果的第个（从右往左，从开始计数）二进制位为，那么我们就将对应的贡献计入答案。

相关位运算操作：

• ： 判断的二进制最右一位是否为，在数学上等价于取余数；
• ：将右移一位，可理解为删除最低位，在数学上等价于向下整除。

具体代码实现如下：

public double myPow(double x, int n) {
    if (n == 0) {
        return 1;
    }
    long N = n;
    return N < 0 ? 1 / recur(x, -N) : recur(x, N);
}

private double recur(double x, long n) {
    double ans = 1.0;
    // 贡献的初始值为 x
    double x_contribute = x;
    // 在对 n 进行二进制拆分的同时计算答案
    while (n > 0) {
        if ((n & 1) == 1) {
            // 如果 n 二进制表示的最低位为 1，那么需要计入贡献
            ans *= x_contribute;
        }
        // 将贡献不断地平方
        x_contribute *= x_contribute;
        // 舍弃 n 二进制表示的最低位，这样我们每次只要判断最低位即可
        n = n >> 1;
    }
    return ans;
}

• 时间复杂度：，即为对进行二进制拆分的时间复杂度。
• 空间复杂度：。