为什么要学习复杂度分析？
我们用开发工具将代码跑一遍，通过统计和监控就能得到算法执行的时间和占用的内存，为什么还要做算法的时间和空间复杂度分析？这种统计复杂度的方法我们称为"事后统计法 ",这种统计方法有如下局限性：
- 测试结果依赖测试环境
- 测试结果受数据估摸影响很大
所以我们需要一个不需要具体数据和环境就能粗略估算算法执行效率的方法。
大O复杂度表示法
复杂度分析包括：
- 时间复杂度分析
- 空间复杂度分析
时间复杂度
我们假设没句代码执行的时间都是一个unit_time，因此所有代码的执行时间T(n)与每行代码的执行次数n成正比，把这个规律总结成一个公式：
这就是大O时间复杂度表示法：
- T(n)表示代码执行的时间
- n表示数据规模的大小
- f(n)表示每行代码执行的次数总和
- O表示代码的执行时间T(n)与f(n)成正比
大O时间复杂度表示代码执行时间随数据规模的增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。当n很大时，比如1000000，公式中的低阶、常量、系数并不左右增长的趋势可以忽略。例如T(n) = O(n+1)或T(n) = O(n²+2n+1)，用大O表示法可以记为T(n) = O(n)、T(n) = O(n²)。
时间复杂度分析
时间复杂度分析的技巧
只关注循环执行次数最多的一段代码
大O表示的是一种变化趋势，所以我们只需要关注最大阶的量级就可以了。例如一个函数，有一个for循环执行n次，其余代码均只执行一次，那么这个函数的时间复杂度就O(n)；一个函数有一个for循环执行n次，还有一个for循环执行n²次，那这个函数的时间复杂度就是O(n²)。加法法则
两个函数的时间复杂度相加，总的复杂度等于量级最大的那段代码的复杂度，原因同上一个技巧的解锁。这里要注意一点，如果某个函数里面for循环循环执行10000次，而另一个函数循环执行n次，那这两个函数相加后总的复杂度为O(n)，因为大O表示的是一种变化趋势，只要是个确定的数，不论多么大都与n无关，是常量阶，这种当n趋于无限大时都可以忽略。乘法法则
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，例如一个n次for循环嵌套另一个n次for循环，时间复杂度为O(n²)。
常见的复杂度量级
常量阶O(1)
只要代码不随n的增大而增大，时间复杂度就是O(1)对数阶O(logn)
线性阶O(n)
线性对数阶O(nlogn)
k次方阶O(n^k)
指数阶O(2^n)
阶乘阶O(n!)
空间复杂度
空间复杂度表示算法的存储空间与数据规模之间的增长关系
空间复杂度的分析同时间复杂度。
最好、最坏情况时间复杂度
最好情况时间复杂度
在最理想的情况下，执行一段代码的时间复杂度最坏情况时间复杂度
在最糟糕的情况下，执行一段代码的时间复杂度
平均情况时间复杂度
最好、最坏情况时间复杂度反映的是极端情况下的复杂度，发生的概率不大。平均情况时间复杂度是将每种情况发生的概率考虑进去，将每种情况下的复杂度乘以发生这种情况的概率相加，这个值是概率论中的加权平均值，也叫期望值。所以平均时间复杂度也称加权平均时间复杂度或期望时间复杂度。
均摊时间复杂度
对一个数据结构进行一组连续的操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，且这些操作之间存在前后连贯的时序关系，这种情况下，我们将这一组操作放在一起分析，看能否将时间复杂度较高的那次操作的耗时，分摊到其他那些时间复杂度低的操作上，这就是摊还分析法。通过摊还分析法得到的时间复杂度，我们称为均摊时间复杂度。一般均摊时间复杂度就等于最好时间复杂度。
如上图，共n+1种情况，每种情况发生的概率都一样，前n种情况的时间复杂度为O(1),第n+1种情况的时间复杂度为O(n)，那平均时间复杂度为O(1)。因此，均摊时间复杂度就是一种特殊的平均时间复杂度。只是针对这种特殊场景，我们不需要再找出所有情况及发生的概率计算加权平均值，能够快速得到其时间复杂度。
以上内容是对学习极客时间王争出品的数据结构与算法之美的总结，算法小白去订阅学习吧！
