50.Pow(x, n)

Pow(x, n)

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

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：$2^{-2} = 1/2^2 = 1/4 = 0.25$

提示：

• -100.0 < x < 100.0
• $-2^{31}$ <= n <= $2^{31} - 1$
• n 是一个整数
• $x^n$ 在 $-10^4$ 到 $10^4$ 范围内

解析

快速幂算法：每次将指数减半，底数平方，从而将时间复杂度降到 O(logn)。

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (n === 0) return 1;
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  while (n > 0) {
    if (n & 1) {
      result *= x;
    }
    x *= x;
    n = Math.floor(n / 2);
  }
  return result;
};

快速幂是非常经典的算法：利用 $x^n = (x^2)^{n/2}$ 的性质，将 O(n) 的乘法运算降为 O(logn)。