如何在 JavaScript 中找到 11 的幂或 x 的 n 次幂？

Question

我正尝试找到n的11次幂。我知道在JavaScript中有一个名为Math.pow的函数可以给你数字的幂。我想要自己实现那个函数。我的函数完美地工作了，但它的时间复杂度是O(n)，我们能否使用其他方法减少这个时间复杂度呢？

我正在考虑使用位图，但是没有成功。

function power(x,n) {
    let sum =1
    for(let i =0;i<n;i++){
    sum*=x
    }
    
    return sum
}

console.log(power(11,3))

- user5711656

---

双星号 ** 是允许的吗？为什么不行，有什么替代方法？ - Nina Scholz

你听说过平方幂运算吗？ - Putnam

你看过这个了吗？ - hgb123

@user268396 如何实现 O(logn)。 - user5711656

可以使用 log 和 exp 函数吗？ - MBo

Answer 1

一种可能的方法：

function power(x, n) {
  let res = 1;
  let acc = x;
  while (n > 0) {
    if (n & 1) res *= acc;
    acc *= acc;
    n >>= 1;
  }
  return res;
}

console.log(power(11, 0)); // 1
console.log(power(11, 1)); // 11
console.log(power(11, 2)); // 121
console.log(power(11, 3)); // 1331
console.log(power(11, 5)); // 161051
console.log(power(11, 8)); // 214358881 etc.

这个想法是记忆原始数字（x）的平方结果。每一步都将n减半，因此时间复杂度为O(log n)，而不是O(n)。它与@NinaScholz的解决方案非常相似，但是它是迭代的，而不是递归的（我认为这是一个好处）。

（是的，在任何真实的应用程序中，肯定也应该检查MAX_SAFE_INTEGER，但我想我们正在讨论一个算法）

- raina77ow

---

复杂度是什么？ - user5711656

对我来说似乎是O(log(n))，但我并不擅长阅读这些。 - jonatjano

Answer 2

你可以使用提出的平方方法。

复杂度为O(log₂(n))，就像此函数计数表格一样。

   n     counts
-------  ------
   100      7
  1000     10
 10000     14
100000     17

function power(x, n) {
    if (n === 1) return x;
    let temp = power(x, n >> 1);
    return n % 2
        ? x * temp * temp
        : temp * temp;
}

console.log(power(11, 3)); // 1331 with 2 calls

- Nina Scholz

---

@naina 什么是复杂度？ - user5711656

Answer 3

这是一个直接的JavaScript实现方案:

function exp_by_squaring(x,n){
   if(n < 0) 
     return exp_by_squaring(1 / x, -n);
   else if(n === 0) 
     return  1;
   else if(n === 1) 
     return  x ;
   else if(n %2===0) 
     return exp_by_squaring(x * x,  n / 2);
   else 
     return x * exp_by_squaring(x * x, (n - 1) / 2);
}

我还使用其他回答中的一些方法创建了一个基准测试，看看这个链接：

Benchmark

- Greedo

---

那个基准测试是没有意义的，因为你只是一遍又一遍地计算相同的功率。这很可能被优化掉了。 - Jan Schultke

每个测试应该是独立的，因此在测试之间应该清除内存。 - Greedo

你仍然在计算 pow(11, 3)，对于所有方法来说大致相同。至少需要一个更大的指数才能看到显著的差异。 - Jan Schultke

是的，我同意这一点，在较大计算中差异更为明显。在链接中，原帖作者可以更改值并注意到差异。 - Greedo

Answer 4

这个实现比你原来的更快，虽然不够优雅

function power(x,n){
   return Array.apply(null,Array(n)).reduce((r,v) => r*x, 1)
}

- user14061659

---

这种方法会更慢，因为 reduce 和 apply 包含了开销。 - Greedo

如果你真的认为这样更快，请提供证明或任何有意义的解释。 - Asad S

Answer 5

我还不能直接评论你的问题，但我希望我足够理解你的问题。这是你正在寻找的东西吗？

const myPow = (x, y) => x ** y;

- Rick van den Broek