问题：求，为了简化，假设x和n都是大于等于0的整数：
一般来说 如果直接使用遍历的话，需要运行n次，记为：时间复杂度O(n)，Python实现如下：
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是正确的，为了方便观察遍历运算了几次，我们把函数里添加一个计数的变量，每次遍历让他+1：
def power(x, n):
k = 0 # 计算循环次数
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)
现在来优化一下这个算法：
根据中小学学到的数学知识，我们可以了解到：
易得：
n为偶数时
n为奇数时
转化为Python，使用递归后 可以写出以下内容：
def power(x, n):
print(x, n) # 为了方便观察递归的次数和每次带入的参数
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( )
