O标记法与常见时间复杂度

算法 : 内功心法, 是解决问题的一种思想

时间复杂度 T(n)T(n)

由于每台机器的性能有所差别,所有其执行相同代码的时间也长短不一,故而推出一种计量方式,统计代码执行基本运算(函数调用需要看其源码的基本运算)的数量(n) 来确定一个算法的优劣,其中基本运算的循环按乘法计算,顺序结构按加法计算,分支结构取最大值

for a in range(0, 1000): 
    for b in range(0, 1000):
        for c in range(0, 1000):
            if a+b+c == 1000 and a**2 + b**2 + c**2:
                print('a,b,c,: {}, {}, {}'.format(a,b,c))

上述代码的时间复杂度为
T=1000100010002T = 1000 * 1000 * 1000 * 2
那么如果将上述代码中的 1000 改为 2000, 则
T=2000200020002T = 2000 * 2000 * 2000 * 2
由于上述同样的代码由于不同的参数的 T 都不同,我们便将其统一成 N,这样上述代码的时间复杂度可以表示成:
T=NNN2T = N * N * N * 2
同样的我们抓住其主要 “矛盾” ,观其大,再将其简化成
T=N3T= N^3
这样同一段代码的时间复杂度便不会根据其参数而发生改变了。

OO 标记法 O()O()

其实和求极限的原理相似,抓住问题的主要矛盾,忽略那些细枝末节,也就像前面的 TT的最后的样子。

时间复杂度的几条基本规则

  1. 基本步骤: 即只有常数项, 算作 O(1)O(1)

  2. 基本结构顺序, 条件, 循环

    • 顺序结构: 按加法运算

    • 循环结构: 乘法

    • 分支结构: 取最大值

  3. 判断一个算法效率, 往往只需要关注操作数量的最高次项, 其他次要的忽略

  4. 没特殊说明, 分析的时间复杂度都是最坏时间复杂度

常见的时间复杂度

TT OO 名称
1212 O(1)O(1) 常数阶
2n+32n+3 O(n)O(n) 线性阶
3n2+2n+13n^2+2n+1 O(n2)O(n^2) 平方阶
5log2n+205log2n+20 O(log(n))O(log(n)) 对数阶
2n+3nlog2n+192n+3nlog2n+19 O(nlog(n))O(nlog(n)) nlog(n)nlog(n)
6n3+2n2+3n+46n^3+2n^2+3n+4 O(n3)O(n^3) 立方阶
2n2^n O(2n)O(2^n) 指数阶
20190526105531-时间复杂度曲线图

O(1)<O(log(n))<O(n)<O(nlog(n))<O(n2)<O(n2log(n))<O(n3)<O(2n)<O(n!)<O(nn)O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2)< O(n ^ 2log(n)) < O(n^3) < O(2^n) < O(n!) < O(n^n)