實(shí)現(xiàn) pow(x, n) 膘侮，即計(jì)算 x 的 n 次冪函數(shù)。
示例 1:
輸入: 2.00000, 10
輸出: 1024.00000
當(dāng)指數(shù)為負(fù)數(shù)的時(shí)候颤诀，可以轉(zhuǎn)化為底數(shù)取導(dǎo)數(shù)，指數(shù)取相反數(shù)的情況，這一點(diǎn)并不難理解温亲。
if n < 0:
x = 1 / x
n = -n
方法1: 暴力破解法
def mypow1(self, x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
for i in range(n):
ans = ans * x
return ans
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)O(n). 我們需要將 x 連乘 n 次。
空間復(fù)雜度：O(1)O(1). 我們只需要一個(gè)變量來(lái)保存最終 x 的連乘結(jié)果杯矩。
方法2:快速冪算法(遞歸)
假定我們已經(jīng)得到了 x ^ nx
n
的結(jié)果栈虚，我們?nèi)绾蔚玫?x ^ {2 * n}x
2?n
的結(jié)果？很明顯史隆，我們不需要將 x 再乘 n 次魂务。使用公式 (x ^ n) ^ 2 = x ^ {2 * n}(x
n
)
2
=x
2?n
，我們可以在一次計(jì)算內(nèi)得到 x ^ {2 * n}x
2?n
的值。使用該優(yōu)化方法粘姜，我們可以降低算法的時(shí)間復(fù)雜度鬓照。
def mypow3(self, x, n):
if n < 0:
x = 1 / x
n = -n
return self.fastPow(x, n)
def fastPow(self, x, n):
if n == 0: return 1.0
half = self.fastPow(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
復(fù)雜度分析
時(shí)間復(fù)雜度：O(logn).
空間復(fù)雜度：O(logn).
方法 3：快速冪算法（循環(huán)）
def mypow2(self, x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
while n:
if n & 1:
ans *= x
x *= x
n >>= 1
return ans
復(fù)雜度分析
時(shí)間復(fù)雜度：O(logn).
空間復(fù)雜度：O(1).
