算法：数值的整数次方算法

文章图片

实现 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 的二进制表示 (1001101)2 中的每个 1！
这样以来，我们从 x开始不断地进行平方，如果n的第 k 个（从右往左，从 0 开始计数）二进制位为 1 ，那么我们就将对应的贡献
x的(2的k次方)次方计入答案。
代码如下：

复杂度分析