實(shí)現(xiàn) pow(x, n) ，即計(jì)算 x 的 n 次冪函數(shù)。
示例 1:
輸入: 2.00000, 10
輸出: 1024.00000
示例 2:
輸入: 2.10000, 3
輸出: 9.26100
示例 3:
輸入: 2.00000, -2
輸出: 0.25000
解釋:
說(shuō)明:
-100.0 < x < 100.0
n 是 32 位有符號(hào)整數(shù)，其數(shù)值范圍是 [?231, 231 ? 1] 。
解法 1
暴力法，x 的 n 次冪就是 n 個(gè) x 相乘，注意處理 n 為負(fù)數(shù)的情況，需要將 x 變?yōu)?x 的倒數(shù)，再將 n 變?yōu)檎龜?shù)
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
執(zhí)行用時(shí)：超出時(shí)間限制
時(shí)間復(fù)雜度：O(n)，我們需要將 x 累乘 n 次。
空間復(fù)雜度：O(1)，我們只需要一個(gè)變量來(lái)保存最終 x 的累乘結(jié)果。
解法 2
利用遞歸實(shí)現(xiàn)分治法，我們可以根據(jù)冪的奇偶來(lái)將公式拆解，使得運(yùn)算數(shù)值盡可能小，從而提升運(yùn)算速度，若為偶數(shù) ，若為奇數(shù)
，注意若 n 為負(fù)數(shù)，
。當(dāng) n 為 1 時(shí)返回 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)
執(zhí)行用時(shí) :40 ms
內(nèi)存消耗 :13.7 MB
時(shí)間復(fù)雜度：O(log n)，每一次我們使用公式 ，n 都變?yōu)樵瓉?lái)的一半。因此我們需要最多 O(log n) 次操作來(lái)得到結(jié)果。
空間復(fù)雜度：O(log n)，每一次計(jì)算，我們需要存儲(chǔ) 的結(jié)果。 我們需要計(jì)算 O(log n) 次，所以空間復(fù)雜度為 O(log n) 。
解法 3
利用迭代實(shí)現(xiàn)二進(jìn)制拆分，由于遞歸需要使用額外的?？臻g，我們可以將遞歸轉(zhuǎn)寫為迭代。我們觀察一下 n 的二進(jìn)制表示，假設(shè) n = 77，二進(jìn)制表示為 1001101，將其包含 1 的部分拆分為 1000000 0001000 0000100 0000001。其中，1000000 的十進(jìn)制表示為 64，0001000 的十進(jìn)制表示為 8，0000100 的十進(jìn)制表示為 4，0000001 的十進(jìn)制表示為 1，而一個(gè)數(shù) 恰好等于
。那么，如果計(jì)算一個(gè)數(shù) x 的 n 次冪，就可以從 x 開始不斷地進(jìn)行平方，得到
如果 n 的第 k 個(gè)（從右往左，從 0 開始計(jì)數(shù)）二進(jìn)制位為 1，那么我們就將
計(jì)入結(jié)果，注意是從 0 開始計(jì)數(shù)，如果 n 的二進(jìn)制第 0 位為 1，則將
計(jì)入結(jié)果，并全部累乘得到最終結(jié)果。
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
執(zhí)行用時(shí) :44 ms
內(nèi)存消耗 :13.8 MB
時(shí)間復(fù)雜度：O(log n)，對(duì) n 進(jìn)行二進(jìn)制拆分的時(shí)間復(fù)雜度。
空間復(fù)雜度：O(1)
