我们都知道，数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。
为什么需要复杂度分析？
如果只掌握了数据结构和算法的特点、用法，但是没有学会复杂度分析，那就相当于只知道操作口诀，而没掌握心法。只有把心法了然于胸，才能做到无招胜有招！
大O 复杂度表示法
所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度。
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
几种常见时间复杂度实例分析
常量阶O(1)
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
O(logn)、O(nlogn)
- 为什么对数阶的时间复杂度都记为 O(logn)，为没有体现对数的“底”？
因为对数之间是可以互相转换的，log3n 就等于 log32 * log2n，其中 C=log32 是一个常量。
- 如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。
O(m+n)、O(m*n)
代码的复杂度由两个数据的规模来决定。
最好、最坏情况时间复杂度
为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。
平均时间复杂度
考虑每种情况发生的概率，得出的值在概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。
均摊时间复杂度
对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
空间复杂度
我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。分析方法参考时间复杂度。
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
参考资料
若有收获，就点个赞吧
0 人点赞
