WinDocs

切换主题

返回顶部
导航栏

在这里插入图片描述

起步

作者:winter wang
更新于:11 天前
字数统计:915 字
阅读时长:3 分钟
阅读量:

求 x 的 n 次幂（先只谈论n非负）

暴力解法

$$x^{n} = x · x · x ··· x$$ (n个x相乘)

【暴力解法】关键步骤

js
let result = 1
while (n > 0) {
  result *= x
  n--
}

循环n次，时间复杂度是O(N)

快速幂

【快速幂】的关键步骤

先举一个例子 求 x 的 100 次幂

暴力解法就是

$$x^{100} = x · x · x ··· x$$ (100个x相乘)

因为100的二进制是1100100，所以

$$100 = 0·2^0 + 0·2^1 + 1·2^2 + 0·2^3 + 0·2^4 + 1·2^5 + 1·2^6 $$

也就是

$$100 = 2^2 + 2^5 + 2^6 $$

所以我们可以简化求解公式

$$x^{100} = x^{2^2} · x^{2^5} · x^{2^6}$$

js
let result = 1
// 当 n === 0 的时候没有进循环，结果就是result === 1
while (n > 0) {
  // 判断当前最低位是否是1
  if ((n & 1) === 1)
    result *= x
  x *= x
  n >>>= 1 // 无符号右移，删除最低位
}

循环 $log_2 N$次，时间复杂度是 O(logN)

LeetCode 50. Pow(x, n)

我们来看LeetCode上的一道求幂的题目 50. Pow(x, n)

关键步骤是一样，主要是要考虑负数次幂的情况

js
const myPow = function (x, n) {
  let result = 1

  let flag = false
  if (n < 0) {
    flag = true
    n = -n
  }

  while (n > 0) {
    if ((n & 1) === 1)
      result *= x
    x *= x
    n >>>= 1
  }
  if (flag)
    result = parseFloat(1 / result)

  return result
}

还有一个更加简洁一点的代码，我给他起名字叫 前处理

js
const myPow = function (x, n) {
  let result = 1

  if (n < 0) {
    x = parseFloat(1 / x)
    n = -n
  }

  while (n > 0) {
    if ((n & 1) === 1)
      result *= x
    x *= x
    n >>>= 1
  }

  return result
}

自然，第一种就是后处理，把正数解求出来，然后在最后取一个倒数就可以了

image.png

可以看到，后处理的效率要比先处理的效率高，这是我第一次提交时候的比较，但是我今天又试了一次

image.png

结果就是这样的了，JS在LeetCode中的效率问题真是一个迷啊~ 我在这里就不做过多讨论了，有机会再研究研究

求大数的幂的最后一位

我们来加大一下难度: 传入的两个非负数字是字符串，可能是很大的数； 同时再简化一下题目~(逃): 返回结果的最后一位即可

【要求】求 $a^b$ 的 最后一位数字，a、b可能会很大

【分析】 求$a^b$的最后一位数字，只要求最后一位，那不管a有多大，我们只需要计算a最后一位c的 $c^b$的结果即可

javascript
let a = +str1[str1.length - 1];

接下来就是快速幂的过程

js
while (b > 0) {
  if ((b & 1) === 1)
    result = (result * a) % 10
  a = (a * a) % 10
  b >>>= 1
}

由于只需要最后一位，所以就在操作（在result与a）中 %10，取到个位数

所以完整代码是这样的

js
function yk(str1, str2) {
  let a = +str1[str1.length - 1]
  let b = +str2
  if (a === 0)
    return 0
  let result = 1

  while (b > 0) {
    if ((b & 1) === 1)
      result = (result * a) % 10
    a = (a * a) % 10
    b >>>= 1
  }

  return result
}

const res = yk('24979', '8')
console.log(res) // 1

字符串重复n次

拓展一下，讲一个字符串str重复count次，我们使用快速幂的思想

更多细节可以看我之前的博文 【青训营】月影老师告诉我写好JavaScript代码的四大技巧——风格优先

js
function repeat(str, count) {
  let result = ''
  while (count > 0) {
    if ((count & 1) == 1)
      result += str
    count >>>= 1
    str += str
  }
  return result
}
const res = repeat('*', 10)
console.log(res) // **********

总结

使用快速幂可以降低求幂次的时间复杂度

快速幂有统一形式，可以进行拓展

Contributors

winter wang