50. Pow(x, n)

快速幂+递归

  1. 解题思路：

    • 对于一个 x 的 n 次方： 如果 n 小于 0 ，x 的 n 次方 等于 1/x 的 -n 次方（此时 -n 为正数）；
    • 如果 n 是一个偶数：x 的 n 次方 等于 x*x 乘以 n/2 次方；
    • 如果 n 是一个奇数：x 的 n 次方 等于 x 乘以 x 的 n-1 次方；
    • 如果 n 等于 0 ，直接返回 1；

  2. 图解：

  3. 复杂度：

    • 时间复杂度：O(logn)，即为递归的层数；
    • 空间复杂度：O(logn)，即为递归的层数，这是由于递归的函数调用会使用栈空间；

  4. 代码实现：

    function myPow(x: number, n: number): number {
  // n=0 直接返回 1
  if (n === 0) return 1;

  // n<0 时 x 的 n 次方等于 1 除以 x 的 -n 次方分
  if (n < 0) return 1 / myPow(x, -n);

  // n 是奇数时 x 的 n 次方 = x*x 的 n-1 次方
  if (n % 2) return x * myPow(x, n - 1);

  // n 是偶数，使用分治，一分为二，等于 x*x 的 n/2 次方
  return myPow(x * x, n / 2);
}

快速幂+位运算

  1. 解题思路：

  2. 复杂度：

    • 时间复杂度：O(logn)，二分的时间复杂度为对数级别；
    • 空间复杂度：O(1)，变量占用常数大小额外空间；

  3. 代码实现：

    function myPow(x: number, n: number): number {
  // 如果 n 小于 0 ，x 的 n 次方 等于 1/x 的 -n 次方（此时 -n 为正数）
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  while (n) {
    // 判断 n 的二进制最后一位是 1，则将结果乘以 x
    if (n & 1) result *= x; 
    // n 是一个偶数：x 的 n 次方 等于 x*x 乘以 x 的 n/2 次方
    x *= x;
    n >>>= 1;
  }

  return result;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 快速幂+递归
    1. 1.1. 快速幂+位运算