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

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

时间复杂度 $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=1000\ast 1000\ast 1000\ast 2$ 那么如果将上述代码中的 1000 改为 2000， 则 $T=2000\ast 2000\ast 2000\ast 2$ 由于上述同样的代码由于不同的参数的 T 都不同，我们便将其统一成 N，这样上述代码的时间复杂度可以表示成： $T=N\ast N\ast N\ast 2$ 同样的我们抓住其主要 “矛盾” ，观其大，再将其简化成 $T=N^3$ 这样同一段代码的时间复杂度便不会根据其参数而发生改变了。

大 $O$ 标记法 $O()$

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

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

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

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

   • 顺序结构: 按加法运算
   • 循环结构: 乘法
   • 分支结构: 取最大值

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

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

常见的时间复杂度

$T$	$O$	名称
$12$	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2+2n+1$	$O(n^2)$	平方阶
$5log2n+20$	$O(log(n))$	对数阶
$2n+3nlog2n+19$	$O(nlog(n))$	$nlog(n)$ 阶
$6n^3+2n^2+3n+4$	$O(n^3)$	立方阶
$2^n$	$O(2^n)$	指数阶

​​

$$O(1)<O(log(n))<O(n)<O(nlog(n))<O(n^2)<O(n^{2}log(n))<O(n^3)<O(2^n)<O(n!)<O(n^n)$$