LeetCode如何實現Pow(x,n)

# LeetCode如何實現Pow(x,n)

## 問題概述

LeetCode上的[Pow(x, n)](https://leetcode.com/problems/powx-n/)問題要求我們實現計算x的n次冪（即x^n）的函數。這個問題看似簡單，但需要考慮多種邊界情況和高效的算法實現。

### 問題描述
- 實現 `pow(x, n)`，即計算x的n次冪
- -100.0 < x < 100.0
- n是32位有符號整數，范圍在[-2^31, 2^31 - 1]
- 結果精度保留5位小數

## 暴力解法（不推薦）

最直觀的解法是直接循環相乘：

```python
def myPow(x: float, n: int) -> float:
    result = 1
    for _ in range(abs(n)):
        result *= x
    return result if n >= 0 else 1/result

問題：當n很大時（如n=2^31），這種O(n)時間復雜度的解法會非常慢，導致超時。

快速冪算法（分治思想）

快速冪算法通過分治策略將時間復雜度降低到O(log n)。

算法原理

1. 將指數n分解為二進制表示
2. 利用公式：x^n = x^(n/2) * x^(n/2) （當n為偶數）
3. 對于奇數n：x^n = x * x^((n-1)/2) * x^((n-1)/2)

遞歸實現

def myPow(x: float, n: int) -> float:
    def quickMul(N):
        if N == 0:
            return 1.0
        y = quickMul(N // 2)
        return y * y if N % 2 == 0 else y * y * x
    
    return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

迭代實現（更高效）

def myPow(x: float, n: int) -> float:
    def quickMul(N):
        ans = 1.0
        x_contribute = x
        while N > 0:
            if N % 2 == 1:
                ans *= x_contribute
            x_contribute *= x_contribute
            N = N // 2
        return ans
    
    return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

邊界情況處理

實際實現時需要特別注意以下邊界情況：

1. n為負數：轉換為計算倒數
2. n = -2^31：直接取反會導致整數溢出，需要特殊處理
3. x為0：0的正數次冪為0，0的負數次冪無定義（題目保證不會出現）
4. x為1或-1：可以直接返回結果避免計算

優化后的完整實現：

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    if x == 0.0:
        return 0.0
    if x == 1.0:
        return 1.0
    if x == -1.0:
        return 1.0 if n % 2 == 0 else -1.0
    
    res = 1.0
    abs_n = abs(n)
    while abs_n > 0:
        if abs_n % 2 == 1:
            res *= x
        x *= x
        abs_n //= 2
    
    return res if n > 0 else 1.0 / res

復雜度分析

• 時間復雜度：O(log n)，每次迭代都將問題規模減半
• 空間復雜度：O(1)，只使用了常數個額外變量

實際應用中的注意事項

1. 浮點數精度：Python的浮點數實現遵循IEEE 754標準，但連續乘法可能導致精度損失
2. 大數處理：雖然題目限制了輸入范圍，但在實際工程中需要考慮更大的數值
3. 異常處理：生產代碼需要添加對異常輸入的處理

擴展思考

1. 模運算下的快速冪：在密碼學中常用到大數的模冪運算，可以結合快速冪算法實現

   def pow_mod(x, n, mod):
      res = 1
      while n > 0:
          if n % 2 == 1:
              res = (res * x) % mod
          x = (x * x) % mod
          n = n // 2
      return res
   

2. 矩陣快速冪：該算法可以推廣到矩陣冪運算，用于解決斐波那契數列等問題

總結

實現pow(x,n)函數的關鍵在于： 1. 使用快速冪算法降低時間復雜度 2. 正確處理各種邊界情況 3. 根據實際需求選擇遞歸或迭代實現

掌握快速冪算法不僅有助于解決這道LeetCode題目，更是理解分治算法思想的重要案例，在后續學習更復雜的算法時會有廣泛應用。 “`