跳至主要內容

0050. Pow(x, n)

ITCharge大约 1 分钟

0050. Pow(x, n)open in new window

  • 标签:递归、数学
  • 难度:中等

题目链接

题目大意

描述:给定浮点数 xx 和整数 nn

要求:计算 xxnn 次方(即 xnx^n)。

说明

  • 100.0<x<100.0-100.0 < x < 100.0
  • 231n2311-2^{31} \le n \le 2^{31} - 1
  • nn 是一个整数。
  • 104xn104-10^4 \le x^n \le 10^4

示例

  • 示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000
  • 示例 2:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

解题思路

思路 1:分治算法

常规方法是直接将 xx 累乘 nn 次得出结果,时间复杂度为 O(n)O(n)

我们可以利用分治算法来减少时间复杂度。

根据 nn 的奇偶性,我们可以得到以下结论:

  1. 如果 nn 为偶数,xn=xn/2×xn/2x^n = x^{n / 2} \times x^{n / 2}
  2. 如果 nn 为奇数,xn=x×x(n1)/2×x(n1)/2x^n = x \times x^{(n - 1) / 2} \times x^{(n - 1) / 2}

x(n/2)x^{(n / 2)}x(n1)/2x^{(n - 1) / 2} 又可以继续向下递归划分。

则我们可以利用低纬度的幂计算结果,来得到高纬度的幂计算结果。

这样递归求解,时间复杂度为 O(logn)O(\log n),并且递归也可以转为递推来做。

需要注意如果 nn 为负数,可以转换为 1x(n)\frac{1}{x} ^{(-n)}

思路 1:代码

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0:
            return 0.0
        res = 1
        if n < 0:
            x = 1/x
            n = -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n)
  • 空间复杂度O(1)O(1)