1.算法性能评估-python

概论

  • 时间复杂度
  • 空间复杂度

时间复杂度

  • 规模: 不同量级有不同的速度,比如水 vs 水杯: 水
  • 测试环境: 在不同测试环境,速度也不同,比如手机 vs 电脑: 电脑

大 O 表示法

def tmp(n):
    add = 0
    for i in range(n):
        add += i
    return add

运行时间:T(n) = (2n + 1) * unit

T(n) = O(f(n)) , O表示 T(n) 与 f(n) 成正比

O 表示渐近时间复杂度

表示代码执行时间随数据规模增长的变化趋势

当 n 很大时,低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略.就可以记为:T(n) = O(n); T(n) = O(n2)。

只关注循环次数多的代码

def tmp(n):
    add = 0
    for i in range(n):
        add += i
    return add

O(n)

选大量级

def tmp(n):
    for i in range(999):
        print(123)

    for i in range(n):
        print(1)

    for i in range(n):
        for j in range(n):
            print(2)

O(n2)

嵌套循环要乘积

def tmp(n):
    for i in range(n):
        a(i)

def a(n):
    for i in range(n):
        print('c')

O(n2)

常见复杂度分析

  • 非多项式量级(过于低效) : O(2n) 和 O(n!)。

  • 多项式量级:O(1), O(logn), O(n), O(nlogn), O(nk)

O(1)

a=2
b=3
d=4

O(logn)

def tmp(n):
    i = 1
    while i < n :
        i = i * 2

i = 20,21, 22, 23…2x

退出循环的条件是 : 2x = n ,即 x = log2n,时间复杂度为 O(log2n)

def tmp(n):
    i = 1
    while i < n :
        i = i * 3

log3n 就等于 log32 * log3n,所以 O(log3n) = O(C * log2n),其中 C=log32 是一个常量。基于我们前面的一个理论:在采用大 O 标记复杂度的时候,可以忽略系数,即 O(Cf(n)) = O(f(n))。所以,O(log2n) 就等于 O(log3n)。因此,在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为 O(logn)

O(m+n)、O(m*n)

def tmp(m, n):
    for i in range(m):
        print(1)

    for i in range(n):
        print(2)

空间复杂度

  • 渐进时间复杂度:表示算法的执行时间与数据规模之间的增长关系。
  • 渐进空间复杂度:表示算法的存储空间与数据规模之间的增长关系。

def tmp(n):
    a = [1]*n
    for i in a:
        print(i)

空间复杂度是: O(n)

这个地方是不是写错了?应该是log3n = log32 * log2n

1 Like
关闭