刷题笔记(1):力扣-50.Pow(x,n): 快速幂算法

本题来自 leetcode 题库第 50 题:50.Pow(x,n),要求使用乘法实现乘幂计算,难度中等。本文介绍了官方给出的“快速幂”算法,并给出了其他方法和思考。

题目描述

实现 pow(x, n) ,即计算 \(x\)\(n\) 次幂函数(即,\(x^n\) )。

  • 示例 1:
    输入:x = 2.00000, n = 10
    输出:1024.00000

  • 示例 2:
    输入:x = 2.10000, n = 3
    输出:9.26100

  • 示例 3:
    输入:x = 2.00000, n = -2
    输出:0.25000
    解释:2-2 = 1/22 = 1/4 = 0.25

  • 提示:
    \(-100.0 < x < 100.0\)
    \(-2^{31} \leqslant n \leqslant 2^{31}-1\)
    \(-10^4 \leqslant x^n \leqslant 10^4\)

这里题目中应明确 \(n\) 为整数

题解

解法1 暴力解法

根据乘幂的定义,将 \(n\)\(x\) 相乘即可计算出结果。时间复杂度为 \(O(n)\),空间复杂度 \(O(1)\)。 此法不赘述。

解法2 快速幂算法 + 递归

这里我们只考虑计算 \(n\geqslant0\) 时的情况,若 \(n<0\) 只需返回 \(1/x^{-n}\)

考虑计算 \(x^n, n\geqslant0\)。当 \(n\) 为偶数,有

\[ x^n = x^{\frac n2} \times x^{\frac n2} \]

\(n\) 为奇数时,有

\[ x^n = x^{\lfloor n/2\rfloor}\times x^{\lfloor n/2\rfloor} \times x \]

据此我们发现 \(x^n\) 可以写作两个 \(x^k\) 相乘(根据情况可能额外多乘 \(x\))。类似地,\(x^k\) 也可以写作两个数相乘。整理如下:

\[ x^n = \begin{cases} 1, & n=0 \\ x^k \times x^k, & n>0且为偶数 \\ x^k \times x^k \times x, &n>0且为奇数 \end{cases} \]

其中,\(x^k=x^{\lfloor \frac n2\rfloor}\)。此时我们便明确了递归算法的子问题以及返回条件。

根据以上分析,写出递归函数:

1
2
3
4
5
function _pow(x, n) {
if (n === 0) return 1
const xk = _pow(x, Math.floor(n / 2))
return n % 2 === 0 ? xk * xk : xk * xk * x
}

然后对 \(n<0\) 的情况稍作处理即可。最后提交的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function (x, n) {
function _pow(x, n) {
if (n === 0) return 1
const xk = _pow(x, Math.floor(n / 2))
return n % 2 === 0 ? xk * xk : xk * xk * x
}
return n < 0 ? 1 / _pow(x, -n) : _pow(x, n)
}

该算法的时间复杂度为 \(O(\log n)\),空间复杂度为 \(O(\log n)\)

解法3 快速幂算法 + 迭代

一般而言,递归算法都可以通过改写成迭代算法来避免对栈的使用,从而降低空间复杂度。下面介绍快速幂算法的迭代版本。

快速幂算法的降低时间复杂度的核心在于将 \(x^n\) 逐步拆分为两个 \(x^k\) 的乘积。由于递归是从 \(n\) 开始逐步分解,而迭代则与递归的方向相反。我们试着从递归算法中找到这些 \(x^k\) 的规律。

对于 \(x^{77}\),由递归算法,可以发现 (这里注意到,这里分解的过程与二进制转化过程一致)

\[ \begin{aligned} x^{77} &= x^{38} \times x^{38} \times x\\ x^{38} &= x^{19} \times x^{19} \\ x^{19} &= x^{9} \times x^{9} \times x \\ x^{9} &= x^{4} \times x^4 \times x \\ x^4 &= x^2 \times x^2 \\ x^2 &= x \times x \\ x &= x \end{aligned} \]

\[ x^{77} = ((((((x)^2)^2)^2 \times x)^2 \times x)^2)^2 \times x \]

我们从右向左整理上式,得到

\[ \begin{aligned} x^{77} &= x\times x^{2\times2} \times x^{2\times2\times2} \times x^{2\times2\times2\times2\times2\times2} \\ &= x^{2^0} \times x^{2^2} \times x^{2^3} \times x^{2^6} \\ &=x^{2^0 + 2^2+2^3+2^6} \end{aligned} \]

得到

\[ 77=2^0 + 2^2+2^3+2^6 \]

可以发现,上式即将 \(77\) 做二进制转换。

\[ 77 = (1001101)_2 \]

通过上面的例子可以发现,求 \(x^n\) 可以转化为求下式:

\[ x^{n} = x^{k_0\times2^0+k_1\times 2^1\times\cdots+k_m\times 2^m} \]

其中,\(k\in\{0,1\}\),序列 \(k_m\cdots k_1k_0\) 即为 \(n\) 的二进制表示。

通过以上讨论可以发现,当需要计算 \(x^n\) 时,先将 \(n\) 转换为二进制。当 \(2^i\) 数位上为 \(1\) 时则乘以一个 \(x^{2^i}\)。具体地,还以 \(x^{77}\) 为例。

首先将 \(77\) 转为二进制 \(1001101\),则有

\[ x^{77} = x^{2^6} \times x^{2^3} \times x^{2^2} \times x \]

具体的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function (x, n) {
function _pow(x, n) {
let base = x
let res = 1
while (n > 0) {
if (n % 2 === 1) {
res *= base
}
base *= base
n = Math.floor(n / 2)
}
return res
}
return n < 0 ? 1 / _pow(x, -n) : _pow(x, n)
}

上面的代码中,在转化二进制的过程中同时进行计算。并且每次循环通过 n / 2 来只处理最后一位,此时要记录数位上的要乘的基(base *= base)。

该算法时间复杂度为 \(O(\log n)\),空间复杂度为 \(O(1)\)

另解

上面介绍的快速幂算法的递归和迭代版本非常巧妙的降低了事件复杂度,注意到其关键在于类似“二分”的处理方法。例如,迭代版本的算法中,考虑将 \(n\) 转化成二进制来分解 \(x^n\),那自然想到将 \(n\) 转化成三进制可不可以呢?

转化为三进制的思路与二进制类似,代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var myPow = function (x, n) {
function _pow(x, n) {
let base = x
let res = 1
while (n > 0) {
const remain = n % 3
if (remain === 1) {
res *= base
} else if (remain === 2) {
res *= base * base
}
base *= base * base
n = Math.floor(n / 3)
}
return res
}
return n < 0 ? 1 / _pow(x, -n) : _pow(x, n)
}

类似地,递归算法同样可以转化为“三分化”版本:

1
2
3
4
5
6
7
8
9
10
11
var myPow = function (x, n) {
function _pow(x, n) {
if (n === 0) return 1
x_k = _pow(x, Math.floor(n / 3))
if (n % 3 === 0) return x_k * x_k * x_k
if (n % 3 === 1) return x_k * x_k * x_k * x
if (n % 3 === 2) return x_k * x_k * x_k * x * x
}

return n < 0 ? 1 / _pow(x, -n) : _pow(x, n)
}

以上修改后的两个算法的时间复杂度和空间复杂度不变。

总结与思考

这道题拿到手后只能想到暴力解法,“快速幂”的解法确实很巧妙,但对于我这种算法小白来说很难自己想出来。至于后面“三进制”的版本是在看官方快速幂迭代版本时想到的,其实理论上可以进行任意进制的转化,进制越高循环次数会越少,但循环中的 if 语句会越多,所以“二进制”是个不差的选择。

这道题给出了基于乘法的幂运算实现,那么计算机中的幂运算如何实现的呢?知乎上有一个问题:计算机是怎样进行开方和幂运算的?,回答中有提到与快速幂算法类似的算法,也有提到 \(O(1)\) 复杂度的算法。

另外计算机加法与乘法的计算原理可参考:计算机中是如何实现加法乘法的?