复杂度分析

数据结构和算法是 ''让计算机更快，更省空间解决问题''。

来源：百度

大O复杂度分析法

for(var j = 0;j < n;j++）{ j = 1; for (;j < n;j++){   }}

T(n)=O(2n+n^2);但是我们一般用n^2来代替其时间复杂度。推广到更多形式，即T(n) = O(f(n)),

n:数据规模

f(n)：每行代码执行次数总和

大O时间复杂度表明了代码执行所需时间的一种趋势，所以也叫渐进时间复杂度(asymptotic time complexity)。

一般数据规模足够大时，我们一般看时间复杂度基于几点：

1.循环执行次数最多的一段代码

2.加法原则：总复杂度等于量级最大的那段代码的复杂度

3.乘法原则：嵌套代码的复杂度等于嵌套内外代码的复杂度。如：T1(n)=O(x),T2(n)=O(log(x)),则T1(n)*T2(n) 等于两者的乘机

4.排列和组合......

空间复杂度 ,表示算法的存储空间与数据规模之间的关系。这个可类比上面的几个原则，推理得到其法则。

---

复杂度分析方面：最好情况时间复杂度（best case time complexity)    最坏情况时间复杂度（worst  case time complexity)   平均情况时间复杂度（average case time complexity) 均摊时间复杂度(amortized time complexity)。

如果提前第一个找到元素，并且结束循环，时间复杂度则为 O（1），最好；如果直到最后一个找到，则时间复杂度 O（n），最坏；而平均事件复杂度则为两者的加权平均值。而这个加权平均值则可用概率论的知识求到。

1x1/(n+1)+1x1/(n+1)+... =O(x)

均摊时间复杂度 跟 平均时间复杂度 似乎很像，而它们的应用场景更有限。它更应该叫做均摊分析。1.在代码执行的所有复杂情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且2.发生时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上，基本上均摊结果就是等于低级别复杂度。如时空互换。

复杂度一般分为两种：时间复杂度，空间复杂度。但是这两种复杂度与性能，没有很大关系。比如说：O(n)在运用时，会忽略掉低阶 常数 系数，仅用高阶来表示。它表明的是随数据增加，总体所耗费资源变化的趋势。另外，在实际运用过程中，在相同的电脑上运行所耗费的时间，也是一定范围内的。

数据规模，代码是否易读，访问方式，内存大小，甚至IO密度也影响着更优的算法是否能运用到实际工程上。

在这个过程中，会逐渐发现，系统自带的类，会满足常见需求。但是不深入研究，遇到瓶颈时，特殊的要求却难以实现。