MIT 6.001X 2016 （11）算法复杂度 big O（）

用  O( ) 来描述最坏的情况  表示的是 程序的step 关于 输入的size 的增长率 

e.g.

抓住主要矛盾，忽略次要矛盾

具体主次矛盾顺序：

（这个c 要指明）

具体计算的小tips： 

加法法则和乘法法则

总的来说   就是把一个大块的程序，分成一个个小块 ，然后分别计算他们的 O( )  然后加起来，取主要矛盾

如果遇见 嵌套的 那就两个乘起来

加法取主要矛盾 ，乘法忽略 常数系数

从上面这个例子我们可以看出 当一次stage  调用 两个及多个的时候 其实是O(n^c)  复杂度  

要注意 这个这个复杂度 是指 输入的什么size  假如是数字 一般默认大小  假如序列一般默认 是length

  

O(1):（a）复杂度与输入无关

       （b）只有很少的算法满足条件，但是很多算法的 部分代码 是这个复杂度

       （c）循环和递归也可能是这个复杂度的，但循环或者调用的 次数跟输入无关

O(logn)：

（1）二分法查找，（任何每一步把搜索的空间分为一半（一半是泛指））

  (2)  每一次循环  输入n都要除以某个常数c， 然后循环的条件是 输入满足某个条件 （大于等于0 etc）就是O(logn)  （在具体一点  log以c为底） 

reducing the size of  problem by a constant factor on each stage 

e.g.

O(n)：

(1) 最典型的例子是循环 然后每次循环， 那个条件变量都 用加减 一个常数

O(nlogn)：

O(n^c):

(1) 大部分n的c次方复杂度的算法都是n的二次方

(2) 比较典型的有内嵌循环和递归

O(c^n):

总结：

对于list 来说 index store len  append  这些操作都是O(1)  因为  python  知道怎么找到那个点 然后 干点啥事

但是对于字典来说  基本都是O(n)  因为字典是 无序的，排序不固定 而list 是固定的