LeetCode如何求數值的整數次方

# LeetCode如何求數值的整數次方

## 問題描述
LeetCode上第50題"Pow(x, n)"要求實現計算x的n次冪的函數。具體描述為：實現`pow(x, n)`，即計算x的n次方（即x^n）。這個看似簡單的數學運算，在編程實現時需要特別注意效率和邊界條件。

## 常規解法及其問題

### 暴力循環法
最直觀的方法是使用循環連續相乘：

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

時間復雜度：O(n)
問題：當n很大時（如n=2^31），循環次數過多，會導致超時。

遞歸暴力法

也可以用遞歸實現：

def myPow(x, n):
    if n == 0: return 1
    if n > 0:
        return x * myPow(x, n-1)
    else:
        return 1/x * myPow(x, n+1)

問題：同樣存在效率問題，且遞歸深度過大可能導致棧溢出。

高效解法：快速冪算法

分治思想

快速冪算法基于分治思想，利用冪的以下性質： x^n = x^(n/2) * x^(n/2) （當n為偶數） x^n = x^(n//2) * x^(n//2) * x （當n為奇數）

遞歸實現

def myPow(x, n):
    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)

時間復雜度：O(log n)
空間復雜度：O(log n)（遞歸?？臻g）

迭代實現

更優的空間復雜度可以通過迭代實現：

def myPow(x, n):
    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)

時間復雜度：O(log n)
空間復雜度：O(1)

邊界情況處理

特殊輸入考慮

1. x為0：當x=0且n≤0時數學上無定義，但通常返回0或報錯
2. n為0：任何數的0次方為1（包括0^0，雖然數學上有爭議）
3. n為負數：轉換為正數處理，最后取倒數
4. 溢出處理：特別當x=1.00000，n=INT_MIN時

改進后的完整代碼

def myPow(x: float, n: int) -> float:
    if x == 0:
        return 0.0 if n > 0 else float('inf')  # 簡單處理
    
    def quickMul(N):
        res = 1.0
        x_contri = x
        while N > 0:
            if N % 2 == 1:
                res *= x_contri
            x_contri *= x_contri
            N = N // 2
        return res
    
    return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

算法分析

二進制視角理解

快速冪算法的本質是將指數n表示為二進制形式。例如計算x^13： 13的二進制是1101，所以： x^13 = x^(8+4+1) = x^8 * x^4 * x^1

復雜度對比

實際應用

密碼學中的應用

快速冪算法在RSA加密等密碼學算法中有重要應用，因為大數冪運算是這些算法的核心操作。

數值計算優化

在科學計算中，頻繁的冪運算使用快速算法可以顯著提升性能。

擴展思考

矩陣快速冪

類似的思路可以推廣到矩陣冪運算，用于高效計算斐波那契數列等：

def matrix_pow(mat, power):
    # 實現矩陣的快速冪
    result = identity_matrix
    while power > 0:
        if power % 2 == 1:
            result = matrix_multiply(result, mat)
        mat = matrix_multiply(mat, mat)
        power = power // 2
    return result

模冪運算

在計算大數冪時，常配合模運算防止溢出：

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

總結

求數值的整數次方問題展示了如何通過算法優化將O(n)的時間復雜度降低到O(log n)。關鍵在于： 1. 識別問題可以分解為子問題 2. 利用數學性質避免重復計算 3. 注意邊界條件和特殊輸入 4. 根據場景選擇遞歸或迭代實現

掌握快速冪算法不僅有助于解決LeetCode這類題目，更是理解分治算法和位運算應用的經典案例。 “`