一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu

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

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

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

题目

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

xnx^n

)。

来源:力扣(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。

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

我的更多前端资讯

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

原文链接:https://juejin.cn/post/7225934630506397753 作者:shichuan

(0)
上一篇 2023年4月26日 上午11:07
下一篇 2023年4月27日 上午10:00

相关推荐

发表评论

登录后才能评论