复杂度分析

复杂度分析是整个算法学习的精髓，因此是我们必须要掌握的。

大O表示法

提到复杂度分析，这里我们不得不介绍大O表示法。

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

由上面的例子不难看出一个规律：所有代码的执行时间T(n)，与每行代码的执行次数成正比。

如果假设每行代码的执行时间为uint_time，则上面例子满足如下关系：

                                                                    T(n) = (2n + 3)unit_time

由此可以看出所有代码的执行时间T(n)，与代码的执行次数n成正比。我们可以把这一关系用下面的方法表示：

 其中T(n)，代表所有代码的执行时间，n代表数据规模的大小，f(n)代表每行代码执行次数的总和。O代表T(n)和f(n)成正比关系。

以上的表示方法即为大O时间复杂度表示方法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，所以也叫作渐进时间复杂度，简称时间复杂度。

时间复杂度分析

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

我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。

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

                                                               O(n) + O(n^2) = max(O(n), O(n^2))

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

                                                               O(n) * O(n^2) = O(n^3)

几种常见的时间复杂度

多项式量级

1、常量阶 O(1)
2、对数阶O(logn)
3、线性阶O(n)
4、线性对数阶O(nlogn)
5、平方阶O(n^2)，立方阶O(n^3)……k次阶O(k^n)

非多项式量级

1、指数阶O(2^n)
2、阶乘阶O(n!)

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

复杂度比较

 时间复杂度分类

最好情况时间复杂度：在理想情况下，执行这段代码的时间复杂度。
最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。
平均情况时间复杂度：每种情况的执行次数乘上其对应的发生概率之和，即为加权平均值，也称期望值。
均摊时间复杂度：对于多数情况下的时间复杂度较低，极少数情况下时间复杂度较高，并呈现一定规律性，可以考虑用摊还分析的方法，将复杂度高的情况均摊到所有情况下，进而降低整体的时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度。