算法：数值的整数次方

大家好，欢迎来到IT知识分享网。

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例

• 输入：x = 2.00000, n = 10
• 输出：1024.00000

提示

• -100.0 < x < 100.0
• -2的31次方 <= n <= 2的31次方 -1
• -10的4次方 <= x的n次方 <= 10的4方

方法一：快速幂 + 递归

「快速幂算法」的本质是分治算法。

以示例为例，从 2 开始，每次直接把上一次的结果进行平方，计算3次就可以得到2的10次方值，我们可以按照：

• x → x的2次方 → x的5次方 → x的10次方的顺序。

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

代码如下：

复杂度分析

• 时间复杂度：O(logn)，即为递归的层数（由于每次递归都会使得指数减少一半）。
• 空间复杂度：O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

方法二：快速幂 + 迭代

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。

我们以 x 的77次方 作为例子：

• x → x的2次方 → x的4次方→ x的9次方 → x的19次方 → x的38次方 → x的77次方；

可以发现：

• x的38次方 到 x的77次方 中额外乘的 x 在 x的77次方 中贡献了 x；
• x的9次方 到 x的19次方 中额外乘的 x 在 之后被平方了 2 次，因此在 x的77次方 中贡献了 x的4次方；
• x的4次方 到 x的9次方 中额外乘的 x 在之后被平方了 3 次， 因此在 x的77次方 中贡献了 x的8次方；
• 最初的 x 在之后被平方了 6 次，因此在 x的77次方 中贡献了 x的64次方。

我们把这些贡献相乘，x * x的4次方 * x的8次方 * x的64次方 恰好等于 x的77次方。而这些贡献的指数部分又是什么呢？它们都是 2 的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1，4，8 和 64，恰好就对应了 77 的二进制表示 ()2 中的每个 1！

这样以来，我们从 x 开始不断地进行平方，如果 n 的第 k 个（从右往左，从 0 开始计数）二进制位为 1，那么我们就将对应的贡献

x的(2的k次方)次方 计入答案。

代码如下：

复杂度分析

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

END

本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。