javascript - 如何在javascript中找到11的幂或x是幂n？

Question

我正在寻找 11 n 的力量.我知道在 JavaScript 中有一个函数 Math.pow这给了你数字的力量。我想自己实现这个功能。 我的功能运行良好 ，但其时间复杂度为 O(n) 我们可以使用任何其他方法降低时间复杂度吗？
我正在考虑使用 bit map ，但没有成功。

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

console.log(power(11,3))

Answer 1

您可以采用建议的方形方法。
复杂度是 O(log2(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