Python 简单实例3：幂运算

问题：求 $x^n$ ，为了简化，假设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)

现在来优化一下这个算法：

根据中小学学到的数学知识，我们可以了解到：

$x^{a+b} = x ^a \cdot x^b$

易得：

n为偶数时
$x^n = (x^2)^{ \frac{n}{2}}$
n为奇数时
$x^n = (x^2)^{ \frac{n-1}{2}}\cdot x$

转化为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)

输出结果为：

该算法的时间复杂度为O( $2\log_2 n$ )