問題：求宏粤，為了簡化父腕，假設x和n都是大于等于0的整數(shù)：
一般來說 如果直接使用遍歷的話役耕，需要運行n次，記為：時間復雜度O(n)堡纬，Python實現(xiàn)如下：
def power(x, n):
if n == 0:
return 1
if n == 1:
return x
if x == 0:
return 0
res = 1
for i in range(n):
res = res * x
return res
print(power(2, 10))
返回結果1024是正確的，為了方便觀察遍歷運算了幾次萨脑，我們把函數(shù)里添加一個計數(shù)的變量隐轩，每次遍歷讓他+1：
def power(x, n):
k = 0 # 計算循環(huán)次數(shù)
if n == 0:
return 1
if n == 1:
return x
if x == 0:
return 0
res = 1
for i in range(n):
res = res * x
k = k + 1
print(k)
return res
power(2, 10)
power(2, 20)
power(2, 30)
運行后會依次輸出：10 20 30饺饭，符合時間復雜度是O(n)
現(xiàn)在來優(yōu)化一下這個算法：
根據(jù)中小學學到的數(shù)學知識渤早，我們可以了解到：
易得：
n為偶數(shù)時
n為奇數(shù)時
轉(zhuǎn)化為Python，使用遞歸后 可以寫出以下內(nèi)容：
def power(x, n):
print(x, n) # 為了方便觀察遞歸的次數(shù)和每次帶入的參數(shù)
if n == 0:
return 1
if n == 1:
return x
if n % 2 == 1:
return power(x * x, n//2) *x
else:
return power(x * x, n//2)
power(2,20)
輸出結果為：
2 20
4 10
16 5
256 2
65536 1
該算法的時間復雜度為O( )
