算法时间和空间复杂度分析

image.png

非常糟糕的复杂度 : O(n!) 、O(2^n) 、O(n^2)
比较糟糕的 ：O(nlog n)
可以接受的 ：O(n)
还不错的：O(n)
非常好的：O(logn) 、O(1)

如何计算时间复杂度

• 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O(1)

• 时间复杂度只关注最高数量级，且与之系数也没有关系。

语句频度T(n) = 2 + 2*n + 1，那么时间复杂度为O(2*n + 3) = O(n)
def fun(n):
    count1 = 0
    count2 = 0
    for i in range(n):
        count1 += 1
        count2 += 2
    return count

• 对于「多个循环」，假设循环体的时间复杂度为O(n) 以下例子是 O(nn1) = O(n^2)

def fun(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

• 顺序执行的语句第1部分复杂度为O(n^{2)，第2部分复杂度为O(n)，总复杂度为max(O(n}2), O(n)) = O(n^2)

def fun(n):
    # 第1部分复杂度为O(n^2)
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    # 第2部分复杂度为O(n)
    for i in range(n):
        count += 2
    return count

• 对于「条件判断语句」，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。当n >= 0分支的复杂度最大，即总复杂度为O(n^2)

def fun(n):
    if n >= 0:
        # 第1部分复杂度为O(n^2)
        count = 0
        for i in range(n):
            for j in range(n):
                count += 1
    else:
        # 第2部分复杂度为O(n)
        for i in range(n):
            count += 2
    return count

「总结：时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，就要深入函数进行分析。」

image.png

image.png

image.png

image.png

image.png