【面试-leetcode50】Pow(x, n)（暴力+快速幂算法）

这是leetcode面试刷题一题多解系列的第9篇，重点熟悉快速幂算法。

题目

实现 pow(x, n) ，即计算 x 的
数 n 次幂函数（即，

$x^n$

xn）。

来源：力扣（LeetCode）
链接：leetcode.cn/problems/po…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解1—暴力法

使用普通的循环求解，就是循环n变相乘，重点是注意下负数的情况，代码如下

function pow(x, n) {
  if (n < 0) { // 处理负指数的情况
    x = 1 / x;
    n = -n;
  }
  let res = 1;
  for (let i = 0; i < n; i++) {
    res *= x;
  }
  return res;
}

这种方法的时间复杂度为 O(n)，当 n 很大时，计算时间会非常长。

题解2—快速幂算法

快速幂算法是一种可以快速计算一个数的整数次幂的算法。其基本思想是，将 n 分解为二进制形式，然后根据二进制位上的值来计算对应的幂次方，从而将计算次数降低到 O(logn) 级别，代码如下。

function pow(x, n) {
  if (n < 0) { // 处理负指数的情况
    x = 1 / x;
    n = -n;
  }
  let res = 1;
  while (n > 0) {
    if (n & 1) { // n 的二进制位上的值为 1
      res *= x;
    }
    x *= x;
    n >>>= 1; // 右移一位，相当于除以 2
  }
  return res;
}

快速幂算法的时间复杂度为O(log n)，空间复杂度为O(1)。相比于普通的循环遍历，快速幂算法的时间复杂度有了很大的降低，可以在很短的时间内计算出非常大的幂次方，如计算2^1000。

快速幂算法的核心思想是将指数进行二分，将幂运算转换为多次乘法。同时，在每一次二分过程中，通过使用平方的方式来替代乘法，使得计算速度更快。此外，还可以通过使用位运算来替代除法和取模运算，从而提高计算速度。

我的更多前端资讯

欢迎大家技术交流 资料分享 摸鱼 求助皆可 —链接