时间复杂度(大O表示法)

大O表示法¶

在算法和算法之间可以通过时间来得出算法的执行效率,但是平台应用的不同和运行环境不同可能会有误差,不太可靠
每台机器计算的时间可能不同,但是执行的步骤数量却是差不多的

demo¶

给定一个参数,算出参数内的数值要求 i+c=u 且满足 i2+c2=u**2

import time


def demo1(g):
    n = g + 1 # range算左不算右
    time1 = time.time()
    for i in range(0, n):
        for c in range(0, n):
            for u in range(0, n):
                if i + c + u == g and i**2 + c**2 == u**2:
                    print('i: {:3}, c: {:3}, u: {:3}'.format(i, c, u))
    print('demo1运行时间:', time.time() - time1)


def demo2(g):
    n = g + 1
    time1 = time.time()
    for i in range(0, n):
        for c in range(0, n):
            u = g - i -c
            if i**2 + c**2 == u**2:
                print('i: {:3}, c: {:3}, u: {:3}'.format(i, c, u))
    print('demo2运行时间:', time.time() - time1)


demo1(200)
demo2(200)

算法1假定计算了大概nnn次,但是通过优化(因为u不需要再循环得到,通过i+c+u=n得知u=n-i-c),这样算法2的计算步骤假定n*n次少了整整n倍的计算步骤
就算len22,len21,len20的print和加减也算进计算步骤里走了K步,计算了3步也好,5步也好,但是对于整体算法结构影响不大,我们只考虑算法本身的逻辑,就像是十年前我们的存储空间以mb来算,现在我们买硬盘的时候还会在乎缺少那么几兆的空间?都是按T来算了吧!
我们算法中的K这个无关紧要的,我们的算法忽略这个K之后就变成了N**3

T(n) = n * n * n * 3 # 我们函数需要走的步骤的拆分
T(n) = n * n * n * 5
T(n) = n^3 * K # 算法本身步骤公式

# 这是声明一个g(n)函数, 和我们上面T(n)本身就差了一个 K 而已,那么 T(n) = g(n) * k
g(n) = n^3

忽略掉K之后,g(n)和T(n),无差别了,g(n)保留了T(n)的算法特征,那么g(n)就是T(n)的渐进函数
那么 T(n)就表示了时间复杂度
那么只保留算法特征的n^3就是T(n)的大O表示法
T(n)的时间复杂度就是O(N^3)

最优时间复杂度¶

没什么意义因为并不是所有的执行区间都是最理想的执行效率没有参考价值

最坏时间复杂度¶

提供了一个保证,保证算法在此种的操作程度上一定能完成工作
我们常说的时间复杂度,通常指的一般都是最坏时间复杂度

平均时间复杂度¶

对算法的一个全面评价,反映了算法的特质,但是,这种衡量并没有保证,不是每次计算都会在这个基本操作内完成,有可能提前有可能放缓,难以计算