这是leetcode面试刷题一题多解系列的第9篇,重点熟悉快速幂算法。
题目
实现 pow(x, n) ,即计算
x
的
数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