[LeetCode解題攻略] 50. Pow(x, n)

題目描述

實作 pow(x, n)，即計算 x 的 n 次方（即 x^n），其中 x 是一個浮點數，而 n 是一個整數。

範例

範例 1

輸入: x = 2.0, n = 10
輸出: 1024.0

輸入: x = 2.1, n = 3
輸出: 9.261

範例 3

輸入: x = 2.0, n = -2
輸出: 0.25
解釋: 2^(-2) = 1 / (2^2) = 1/4 = 0.25

限制條件

• -100.0 < x < 100.0
• 2³¹ <= n <= 2³¹-1
• -10⁴ <= xⁿ <= 10⁴

解法一：暴力法

思路：

• 直接從 1 乘到 n，若 n 為負數則計算 1 / (x^n)。

程式碼：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1
        for _ in range(n):
            result *= x
        return result

時間與空間複雜度：

• 時間複雜度：O(n)，如果n很大的話，速度會變得很慢。
• 空間複雜度：O(1)，只用到常數變數。

解法二：遞迴法

思路：

利用指數拆解的技巧：

• 如果 n 是偶數，則：xⁿ = (x^n/2) × (x^n/2)
• 如果 n 是奇數，則：xⁿ = x × xⁿ⁻¹
• 當 n < 0 時，轉換為：xⁿ=1/x⁻ⁿ

透過這種方式，每次計算時 n 都會減半，因此時間複雜度為 O(log⁡n)。

程式碼：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2 == 0:
            half = self.myPow(x, n // 2)
            return half * half
        else:
            return x * self.myPow(x, n - 1)

時間與空間複雜度：

• 時間複雜度：O(log⁡n)，每次遞迴都將 n 減半。
• 空間複雜度：O(log⁡n)，遞迴深度最多為 O(log⁡n)。

解法三：迭代法

思路：

遞迴方法雖然時間複雜度是 O(log⁡n)，但遞迴會使用額外的棧空間，因此可以用迭代方式來節省空間。

我們可以使用 位運算 來加速：

• 如果 n 是奇數，則乘上 x，並讓 n 減 1。
• 將 n 右移一位（相當於 n = n // 2），並讓 x 平方。
• 迴圈直到 n 變為 0。

這樣能夠在 O(log⁡n) 的時間內完成計算。

程式碼：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1
        while n:
            if n % 2 == 1:  # 若 n 是奇數
                result *= x
            x *= x  # x^2
            n //= 2  # n 除以 2
        return result

時間與空間複雜度：

• 時間複雜度：O(log⁡n)，與遞迴版本相同，每次將 n 減半。
• 空間複雜度：O(1)，因為沒有遞迴的額外空間需求。

結論

• 如果 n 很小，暴力法仍然可行，但不推薦。
• 如果 n 很大，最佳解法是 迭代法，因為：
• • 時間複雜度是 O(log⁡n)，比暴力法快很多。
  • 空間複雜度是 O(1)，比遞迴法更省記憶體。