01_O标记法与常见时间复杂度

---

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

---

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

---

2、大O标记法 O(）

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

---

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

1、基本步骤: 即只有常数项, 算作O(1)
2、基本结构顺序, 条件, 循环
  顺序结构: 按加法运算
  循环结构: 乘法
  分支结构: 取最大值
3、判断一个算法效率, 往往只需要关注操作数量的最高次项, 其他次要的忽略
4、没特殊说明, 分析的时间复杂度都是最坏时间复杂度

---

4、常见的时间复杂度

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

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)< O(n ^ 2log(n)) < O(n^3) < O(2^n) < O(n!) < O(n^n)