avatar

pow(x,n)

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。
Related Topics
  • 数学
  • 二分查找
  • \n
  • 👍 533
  • 👎 0
    1. 第一种解法:快速幂+递归
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public double myPow(double x, int n) {
    int N = n;
    return n >= 0 ? quickMUl(x, N) : 1.0/quickMUl(x, N);

    }

    public double quickMUl(double x, int N){
    if(N == 0){
    return 1.0;
    }
    double y = quickMUl(x, N / 2);
    return N%2 == 0 ? y*y : y*y*x;
    }

    时间复杂度 :O(logn) 递归的层数

    空间复杂度:O(logn) 递归的层数

    1. 快速幂+迭代

      从下列公式推算:
      $$
      n=2^{i_0}+2^{i_1}+\cdots+2^{i_k}
      $$
      可以得知

      $$
      x^n=x^{2^{i_0}}x^{2^{i_1}}\cdots*x^{2^{i_k}}
      $$

      所以我们的代码可以改成这样:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      double quickMul(double x, long N) {
      double ans = 1.0;
      // 贡献的初始值为 x
      double x_contribute = x;
      // 在对 N 进行二进制拆分的同时计算答案
      while (N > 0) {
      if (N % 2 == 1) {
      // 如果 N 二进制表示的最低位为 1,那么需要计入贡献
      ans *= x_contribute;
      }
      // 将贡献不断地平方
      x_contribute *= x_contribute;
      // 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可
      N /= 2;
      }
      return ans;
      }

      public double myPow(double x, int n) {
      long N = n;
      return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
      }

      时间复杂度:O(logn)

      空间复杂度:O(1)

    文章作者: 无知的小狼
    文章链接: https://bytedance.press/2020/11/11/20201101/pow(x,%20n)/
    版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 无知的小狼

    评论