剑指 Offer 16. 数值的整数次方

摘要

剑指 Offer 16. 数值的整数次方

本题的方法被称为快速幂算法，有递归和迭代两个版本。这篇题解会从递归版本的开始讲起，再逐步引出迭代的版本。当指数n为负数时，我们可以计算 x^(-n)再取倒数得到结果，因此我们只需要考虑n为自然数的情况。

一：快速幂 + 递归

快速幂算法的本质是分治算法。举个例子，如果我们要计算x^64，我们可以按照:

的顺序，从x开始，每次直接把上一次的结果进行平方，计算6次就可以得到 x^(64)的值，而不需要对 x乘 63次x。再举一个例子，如果我们要计算 x^77，我们可以按照：

的顺序，在 x→x^2，x2→x^4，x19→x^38 这些步骤中，我们直接把上一次的结果进行平方，而在 x4→x^9，x9→x19，x38→x77这些步骤中，把上一次的结果进行平方后，还要额外乘一个 x。直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 xx。但如果我们从右往左看，分治的思想就十分明显了：

• 当我们要计算 x^n时，我们可以先递归地计算出 y=x⌊n/2⌋，其中⌊a⌋表示对a进行下取整；
• 根据递归计算的结果，如果 n为偶数，那么 x^n=y^2；如果n为奇数，那么 x^n=y^2×x；
• 递归的边界为n=0，任意数的0次方均为1。

由于每次递归都会使得指数减少一半，因此递归的层数为 O(log⁡n)，算法可以在很快的时间内得到结果。

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}
}

复杂度分析

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

二、快速幂 + 迭代

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

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

复杂度分析

• 时间复杂度：O(log⁡n)，即为对n进行二进制拆分的时间复杂度。

• 空间复杂度：O(1)。

博文参考

《leetcode》