解題說明
Pow(x, n)
題目描述：實作函式 pow(x, n)，計算 x 的 n 次方，其中 n 可為正整數、零或負整數。
解題思路：樸素做法將 x 連乘 n 次，時間複雜度 O(n)，當 n 很大時（如 2^31-1）會超時。快速冪（Binary Exponentiation） 利用以下遞推式將複雜度降至 O(log n)：
- 若 n 為偶數：x^n = (x²)^(n/2)
- 若 n 為奇數：x^n = x × (x²)^(n/2)
- 若 n < 0：x^n = (1/x)^(-n)
實作細節：n 可能為 INT_MIN（-2147483648），直接取負數會溢位，因此需用 long 型別存放 n。可以使用遞迴或迭代（位元操作）實作，本解法選用迭代版本以避免遞迴堆疊開銷。
迭代版本：將 n 的二進制表示的每個位元視為是否要累乘對應的 x 的冪次。
C++ 解法
複雜度分析
時間複雜度：O(log n) — 每次迭代將指數減半，共需 log₂(n) 次迭代。
空間複雜度：O(1) — 迭代版本只需常數空間；遞迴版本則為 O(log n) 的呼叫堆疊深度。
虛擬碼
1. Store n as long exp to avoid INT_MIN overflow 2. If exp < 0: set x = 1/x, exp = -exp 3. result = 1.0 4. While exp > 0: a. If exp is odd: result *= x b. x = x * x (square the base) c. exp = exp / 2 (halve the exponent) 5. Return result
其他解法
遞迴快速冪 O(log n)：直接以遞迴實作 myPow(x, n/2)，若 n 為奇數再多乘一次 x。寫法更簡潔，但遞迴堆疊深度為 O(log n)，不如迭代節省空間。
樸素連乘法 O(n)：直接迴圈連乘 x 共 n 次。概念最直觀，但 n 可達 2^31-1，在效能要求高的場合無法通過，僅適合學習理解用。
延伸思考
- 若要計算矩陣的 n 次方（Matrix Exponentiation），如何修改此演算法？這在哪些問題中有應用？
- 若 x 和 n 都是任意大整數（不限於 double 精度），應如何處理精度問題？
- 快速冪的「將指數減半」思想與哪些其他演算法有相似之處（例如 GCD、快速排序）？