02. 快速幂

原理

快速幂的原理很简单，就是利用已经计算过的乘法结果继续参与计算，把乘法的次数减少到最少。比如计算 5^10，先计算 5*5 得到 25，再计算 25*25 得到 625，再计算 625 * 5（5^5）得到 3125（5^5）最后计算 3125*3125（5^10）得到结果。

5 * 5       = 25 (5^2)
25 * 25     = 625 (5^4)
625 * 5     = 3125 (5^5)
3125 * 3125 = 9765625 (5^10)

1
2
3
4

若按照 5*5*... 的顺序依次计算，则要计算 10 次乘法。使用快速幂，只需要 4 次乘法。

由以上分析，可得出如下递推公式：

递归写法

按照上述递推公式，很容易写出递归写法。

const quickPow = (x, n) => {
  if (n < 0) {
    x = 1 / x
    n *= -1
  }
  if (n === 0) return 1
  if (n & 1) return quickPow(x, n - 1) * x
  const temp = quickPow(x, n / 2) 
  // 注意这里需要存一个 temp，减少乘法次数
  return temp * temp
}

quickPow(5, 10) // 9765625

1
2
3
4
5
6
7
8
9
10
11
12
13

迭代写法

递归写法有时候很容易爆栈，更常用的是迭代写法。

const quickPow = function (x, n) {
  let ans = 1
  if (n < 0) {
    x = 1 / x
    n = -n
  }
  while (n) {
    if (n & 1) ans *= x
    x *= x
    n = Math.floor(n / 2)
  }
  return ans
}

quickPow(5, 10) // 9765625

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

02. 快速幂 #

原理 #

递归写法 #

迭代写法 #

02. 快速幂

原理

递归写法

迭代写法