代码随想录01：算法性能分析

时间复杂度分析

O(n)文章源自十年又十年-https://www.bbigsun.com/394.html

• 时间换空间

空间复杂度分析

S(n)文章源自十年又十年-https://www.bbigsun.com/394.html

• 空间换时间

递归算法的时间复杂度

递归算法的时间复杂度取决于：递归的次数 * 每次递归中的操作次数。文章源自十年又十年-https://www.bbigsun.com/394.html

题目：求 x 的 n 次方？文章源自十年又十年-https://www.bbigsun.com/394.html

方法一：文章源自十年又十年-https://www.bbigsun.com/394.html

• 时间复杂度 O(n)

def function1(x, n):
    result = 1
    for i in range(n):
        result *= x
    return result

方法二：文章源自十年又十年-https://www.bbigsun.com/394.html

• 时间复杂度 O(n)

x^5 = 1*x*x*x*x*x 计算5次文章源自十年又十年-https://www.bbigsun.com/394.html

def function2(x, n):
    if n == 0:
        return 1
    else:
        return function2(x, n-1) * x

方法三：文章源自十年又十年-https://www.bbigsun.com/394.html

• 时间复杂度：O(logn)

x^4 = x^2 * x^2 = x*x * x*x 计算2次
x^5 = x^2 * x^2 * x 计算2次文章源自十年又十年-https://www.bbigsun.com/394.html

def function3(x, n):
    if n == 0: return 1
    if n == 1: return x
    # 空间换时间,不管n为奇数还是偶数，t值一样
    t = function3(x, n/2)
    # 如果n为奇数，多乘以个x返回
    if n%2 == 1: return t*t*x
    # 如果n为偶数，直接返回t值
    return t * t