我们都知道数据结构和算法都是为了让代码运行得更快，并且消耗更少的存储空间，但是我们要怎么才能知道一段代码对时间和空间的损耗？
事后统计法
正常来说我们说代码执行得慢或者占用空间大，都是通过监控系统或者统计得出的结论，这也被叫做事后统计法。
但他也有很多的问题：
- 结果与运行环境强相关
不同的环境往往能得出不同甚至相反的结果。 - 与数据量强相关
在数据量小的时候性能可能非常良好，但是数据量一大，性能突然急剧下降。
大O复杂度表示法
image.png
T(n)：代码执行的时间
n：数据的规模
f(n): 每行代码执行的次数总和
O：代表代码的执行时间T(n)和f(n)成正比
大O时间复杂度表示法，它不代表代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做 渐进时间复杂度，简称 时间复杂度。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 只关注量级最大的那段代码
- 嵌套部分等于嵌套内外复杂度的乘积
常见时间复杂度
image.png
O(1): 只要不存在循环递归，那么时间复杂度就是 O(1)
O(logn)、O(nlogn): 常见于 归并排序、快速排序
O(m+n)、O(m·n): 当代码中存在两个不可评估的数据时，时间复杂度为它们的总和或者乘积
版权声明：笔记部分摘抄自极客时间中的课程及评论区
网友评论