BFE.devAI解答 - JavaScript 代码题
109. 实现`Math.pow()`

可以使用二分法来优化乘法运算的次数，加快计算速度。

具体来说，假设要计算 x 的 n 次方，可以进行以下步骤：

1. 如果 n 为 0，返回 1。
2. 如果 n 为正数，那么先将 n 折半，计算 x 的 n/2 次方的结果，然后再进行平方，得到 x 的 n 次方的结果。
3. 如果 n 为负数，那么先将 n 取相反数，然后再按照步骤 2 进行运算，最后将结果取倒数。

具体实现如下：

function pow(x, n) {
  if (n === 0) {
    return 1;
  }
  if (n > 0) {
    const half = pow(x, Math.floor(n / 2));
    return n % 2 === 0 ? half * half : half * half * x;
  }
  // n < 0
  return 1 / pow(x, -n);
}

在这个实现中，进行了 Math.floor(n / 2) 次乘法运算，时间复杂度为 O(log n)。比起连续进行 n 次乘法运算的时间复杂度 O(n)，效率提升了很多。