什么是复杂度分析
数据结构和算法是用来如何让计算机能使用更短时间、更少空间去解决问题，因此需要从执行时间和占用空间两个纬度来评估数据结构和算法的性能，分别从时间复杂度和空间复杂度来描述性能问题，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模的 增长关系。
为什么要进行复杂度分析
- 和性能测试相比，复杂度分析不依赖与支持环境、成本低、效率高、易操作、指导性强的特点。
- 掌握复杂度分析，有助于编写高性能代码，降低系统开发和维护成本。
如何进行复杂度分析
- 单段代码看高频：比如循环。
- 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
- 嵌套代码取乘积：比如递归，多重循环等
- 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取两个复杂度之和。
常见的复杂度级别
- 多项式阶：随着数据规模的增长，算法复杂度按照多项式的比例增长，包括:
- O( $1$ )-常数阶
- O( $log^n$ )-对数阶
- O( $n$ )-线性阶
- O( $n*log^n$ )-线性对数阶
- O( $n^2$ )-平方阶
- O( $n^3$ )-立方阶
- O($n^k$)-多次方阶
- 非多项式阶：随着数据规模的增长，算法复杂度暴增，这类算法性能极差，包括：O($2^n$)-指数阶、O($n!$)-阶乘阶。
时间复杂度分析的4个概念
- 最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
- 最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
- 平均时间复杂度：代码在所有情况下执行时间的加权平均值。
- 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。