复杂度分析

复杂度分析是整个算法学习的精髓，只要掌握它，数据结构和算法的内容基本就掌握了一半。

大O复杂度表示法

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，简称时间复杂度。

1、只关注循环执行次数最多的一段代码

只要关注for循环执行次数就可以了，执行n次，所以总时间复杂度就是O(n)。

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

以上代码有三个for循环，sum1循环中循环次数是100，跟n无关，复杂度为O(1)，sum2循环中循环次数为n，复杂度为O(n)，sum3循环是双重循环，复杂度为O(n²)。最终复杂度就等于量级最大的那段，也就是O(n²)。

3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

以上代码有两个方法是，每个方法都有一个for循环，复杂度都为O(n)，cal3()方法中调用了f()方法，

根据乘法法则，最终复杂度为O(n²)。

4、常见时间复杂度O(logn)、O(nlogn)

以上代码中，变量i是等比增长的，复杂度就是O(logn)。

空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系，称为空间复杂度。

以上代码，数组a申请了一个大小为n的存储空间，空间复杂度就是O(n)。

最好、最坏情况时间复杂度、平均情况时间复杂度

阅读以上代码，不同情况下，时间复杂度是不一样的。为了表示代码在不同情况下的时间复杂度，我们引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

以上代码中，最好情况时间复杂度是O(1)，最坏情况时间复杂度是O(n)，平均情况时间复杂度需要引入概率，假设要寻找的元素在数组中与不在数组中各占1/2，数组中n个数据，出现在每个位置的概率为1/n，所以根据概率乘法原则，出现在数组中每个位置的概率为1/2n。那么平均时间复杂度的计算过程为：1*1/2n+2*1/2n+3*1/2n+……+n*1/2n+n*1/2 = （3n+1）/ 4 ，这个就是加权平均值。平均时间复杂度是O(n)。

均摊时间复杂度

以上代码，最好情况复杂度为O(1)，数组有空间直接插入数据。最坏情况时间复杂度为O(n)，恰巧数组没有空间需要循环遍历一次。平均时间复杂度为O(1)，数组长度为n，外加如果越界的一次，概率都是1/(n+1)，加权平均的计算过程：1*1/(n+1)+1*1/(n+1)+……+1*1/(n+1)+n*1/(n+1) = O(1)。

我们再来分析这个例子，复杂度为O(1)的情况执行n-1次，才会出现一次O(n)，出现的频率是很有规律的。所以针对这样的特殊场景，我们引入均摊时间复杂度，大致思路就是将耗时最多的那一次O(n)，均摊到n-1次O(1)上，均摊结果就是O(1)。