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/2^2 = 1/4 = 0.25$
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解法 1

暴力法，x 的 n 次幂就是 n 个 x 相乘，注意处理 n 为负数的情况，需要将 x 变为 x 的倒数，再将 n 变为正数

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    ans = 1
    for i in range(n):
        ans = ans * x
    return ans

执行用时：超出时间限制

时间复杂度：O(n)，我们需要将 x 累乘 n 次。
空间复杂度：O(1)，我们只需要一个变量来保存最终 x 的累乘结果。

解法 2

利用递归实现分治法，我们可以根据幂的奇偶来将公式拆解，使得运算数值尽可能小，从而提升运算速度，若为偶数 $x^n=(x\cdot x)^{\frac{n}{2}}$ ，若为奇数 $x^n=x^{n-1}x$ ，注意若 n 为负数， $x^n=\frac{1}{x^{-n}}$ 。当 n 为 1 时返回 x，这是递归的出口。另外，需要注意 x = 0 或 1，n = 0 或 1，n < 0 等情况。

def my_pow(x, n):
    if n == 0:
        return 1.0
    if n == 1:
        return x
    if n < 0:
        return 1 / my_pow(x, -n)
    if n % 2:
        return x * my_pow(x, n - 1)
    return my_pow(x * x, n / 2)

执行用时 :40 ms
内存消耗 :13.7 MB

时间复杂度：O(log n)，每一次我们使用公式 $x^n=(x\cdot x)^{\frac{n}{2}}$ ，n 都变为原来的一半。因此我们需要最多 O(log n) 次操作来得到结果。

空间复杂度：O(log n)，每一次计算，我们需要存储 $x ^ {\frac{n }{2}}$ 的结果。我们需要计算 O(log n) 次，所以空间复杂度为 O(log n) 。

解法 3

利用迭代实现二进制拆分，由于递归需要使用额外的栈空间，我们可以将递归转写为迭代。我们观察一下 n 的二进制表示，假设 n = 77，二进制表示为 1001101，将其包含 1 的部分拆分为 1000000 0001000 0000100 0000001。其中，1000000 的十进制表示为 64，0001000 的十进制表示为 8，0000100 的十进制表示为 4，0000001 的十进制表示为 1，而一个数 $x^{77}$ 恰好等于 $x^{64}\times x^8\times x^4\times x^1$ 。那么，如果计算一个数 x 的 n 次幂，就可以从 x 开始不断地进行平方，得到 $x^2, x^4, x^8, x^{16},\cdots$ 如果 n 的第 k 个（从右往左，从 0 开始计数）二进制位为 1，那么我们就将 $x^{2^k}$ 计入结果，注意是从 0 开始计数，如果 n 的二进制第 0 位为 1，则将 $x^{2^0}$ 计入结果，并全部累乘得到最终结果。

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    ans = 1
    while n > 0:
        if n & 1:
            ans *= x
        x *= x
        n >>= 1
    return ans

执行用时 :44 ms
内存消耗 :13.8 MB

时间复杂度：O(log n)，对 n 进行二进制拆分的时间复杂度。
空间复杂度：O(1)

参考

https://leetcode-cn.com/problems/powx-n/

最后编辑于：2020.05.20 07:23:29