一.复杂度分析解决什么问题
- 复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
- 分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。
二.如何衡量执行效率
- 事后统计法局限性很大,依赖于测试环境和数据规模
- 复杂度分析
- 时间复杂度
大O标记法。算法的执行时间与每行代码的执行次数成正比。
- 只关注循环执行最大的一段代码。
- 加法法则:总的复杂度等于量级最大的那段代码的复杂度。
- 乘法法则:嵌套代码的复杂度等于内外循环复杂度的乘积。
-
几种常见复杂度:image.png
- 时间复杂度
-
空间复杂度
表示算法的存储空间与数据规模之间的增长关系。
image.png