文章目录
一、事后统计法
二、分析预测法 -- 时间、空间复杂度分析法
大 O 时间复杂度表示法
时间复杂度分析方法
1. 只关注循环执行次数最多的一段代码；
2. 加法法则：总的时间复杂度等于量级最大的那段代码的复杂度；
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；
4. 几种常见时间复杂度实例分析
4.1. O(1)
4.2. O(logn)、O(nlogn)
4.3. O(m+n), O(m*n)
5. 最好、最坏、平均和均摊时间复杂度
5.1 最好情况时间复杂度
5.2 最坏情况时间复杂度
5.3 平均情况时间复杂度
5.4 均摊情况时间复杂度

数据结构和算法解决的是快和省的问题，即如何让代码运行的更快，如何让代码更节省存储空间。一个非常重要的考量指标是算法的执行效率，分析方法有事后分析和提前预测两种–事后统计法和时间、空间复杂度分析法。
一、事后统计法
即让代码在计算机硬件上实际运行一遍，并监控和统计出算法执行实际花费的时间和占用的内存。这种方法很正确，但是有如下缺点：

测试结果依赖测试的软硬件环境；
测试结果受数据规模和复杂度的影响很大；
并不能确定运行的算法是否最优。
因此我们需要一种方法，以便在构思和编写算法时，不用实际运行就可以粗略估算和预测算法的执行效率，这可以指导我们编写出符合业务要求且效率高的算法程序。

二、分析预测法 – 时间、空间复杂度分析法
大 O 时间复杂度表示法
作为粗略估计，我们可以认为每行代码执行（读-运算-写）所需要的时间都一样，且假定为单位时间 unit_time。这里有两种情况：目标代码不包含循环；目标代码包含循环。对于前者，很简单，执行完一次就完了，执行时间是个固定值，这没什么好研究的；对于后者，由于非循环部分代码的执行时间是固定的，那么目标代码总体执行时间取决于循环体代码的执行时间，这由循环体行数以及各行循环的次数(可能出现嵌套循环)，方便起见总计为循环 n 次，那么总的执行时间就是 n 的函数了，记为 T(n)。很显然，目标代码的执行时间 T(n) 与数据规模 n 成正比，记为：

其中：T(n) 表示代码执行的时间，n 表示数据规模的大小（循环总次数），f(n)表示每行代码执行的次数总和，O表示正比关系。这就是大 O 时间复杂度表示法。
注意，大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐近时间复杂度，简称时间复杂度。
当 n 很大时，公式 f(n) 中的低阶、常量、系数并不左右增长趋势，可忽略，而只需要关注最大量级的那部分即可。

时间复杂度分析方法
1. 只关注循环执行次数最多的一段代码；
2. 加法法则：总的时间复杂度等于量级最大的那段代码的复杂度；
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n))).

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

注意：复杂度分析无需记忆上述公式，只需多看案例多练习分析，就能掌握。

4. 几种常见时间复杂度实例分析
以上可组略分为两类：多项式量级和非多项式量级。只有 O(2n) 和 O(n!) 属于后者。
非多项式量级的时间复杂度算法，随着数据量的增大，算法执行的时间急剧增加，所以这些算法是非常低效的。

4.1. O(1)
表示算法执行时间为常量的算法。一般情况下，只要算法中不存在循环、递归等操作，该算法的时间复杂度就是常量级。

4.2. O(logn)、O(nlogn)
可通过下面案例理解O(logn)：循环体中 i = i * 2; 的执行次数为 log2n次


 i=1;

 while (i <= n) {

   i = i * 2;

 }

通过对数的换底公式，其他任意底的对数都可以转换成常系数形式的log2n（Clog2n），而常系数又是可以忽略的，所以任意对数复杂度的算法可统一将其复杂度表示为logn。
关于O(nlogn)，通过时间复杂度乘法法则可知，O(nlogn) = O(n) * O(logn)，可简单理解为复杂度为 O(logn) 的代码被循环执行了 n 遍。常见的归并排序、快速排序的时间复杂度就是 O(nlogn)。

4.3. O(m+n), O(m*n)
两个数据规模未知的算法的复杂度有如上表示。

复杂度分析并不难，关键在多练习!

5. 最好、最坏、平均和均摊时间复杂度
5.1 最好情况时间复杂度
5.2 最坏情况时间复杂度
5.3 平均情况时间复杂度
运用概率知识算出的期望值（加权平均值）。

说明：很多时候使用一个复杂度就可以满足需求，只有同一块代码块在不同情况下，时间复杂度有量级的差距时，才会使用最好、最坏和平均来区分。

5.4 均摊情况时间复杂度

一种特殊的平均情况时间复杂度