数据结构与算法2-复杂度分析
时间、空间复杂度分析
事后统计法存在很大的局限性，我们需要一个不用具体的测试数据来测试，就可以粗略估计算法的执行效率的方法。
T(n) = O( f(n) )
T(n)表示代码执行的时间
n表示数据规模
O表示T(n)与f(n)表达式成正比。
1.时间复杂度分析
- 只关注循环次数最多的一段代码
- 总复杂度等于量级最大的那段代码的复杂度
- 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
2.常见时间复杂度实例分析
- O(1) 代码的执行时间不随n的增大而增长。
- O(logn) O(nlogn)：
最常见也是最难分析的复杂度。
如果一段代码的时间复杂度是O(logn)，我们循环执行n次，时间复杂度就变成了O(nlogn)。
归并、快排 -> 对线(nlogn) - O(m+n)、O(m*n)：
3.空间复杂度分析
最好、最坏、平均、均摊时间复杂度
最好情况时间复杂度就是在最理想的情况下，执行这段代码的时间复杂度。
最坏情况时间复杂度就是在最糟糕的情况下，执行这段代码的时间复杂度。
平均情况时间复杂度
均摊时间复杂度（重点是摊还分析思路）