1、为什么要学习复杂度分析？
- 比起跑代码，统计与监控，这种事后分析方法，有很大的局限性。（依赖测试环境、收数据规模影响较大）
- 不需要具体数据，来事前粗略估计算法执行效率的方法。
2、大O复杂度表示法
T(n) = O (f(n))
所有代码的执行时间与每行代码的执行次数成正比
并不表示真正的代码执行时间，而是表示代码执行时间随数据规模的变化趋势，也称渐进时间复杂度。简称时间复杂度
3、如何分析？
- 只关注循环执行次数最多的一段代码
- 减法法则 （总复杂度=量级最大那段代码的复杂度）
- 乘法法则 （嵌套代码复杂度=嵌套内外代码复杂度的乘积）
4、 常见的时间复杂度量级
-
常量阶 O(1)
-
对数阶 O(log n)
-
线性阶 O(n)
-
线性对数阶 O(nlog n)
-
平方阶 O(n2)、立方阶(n3)、k次方阶(nk)
-
指数阶 O(2n)
-
阶乘阶 O(n!)
O(m) + O(n)
5、空间复杂度分析
时间复杂度表示：算法的执行时间与数据规模之间的增长关系。
空间复杂度表示：算法的存储空间与数据规模之间的增长关系。
常见的空间复杂度：
O(1)、 O(n)、 O（n2）
6 学习思路
多练习。看到代码多进行分析
Note: 下面下面是之前写过的一篇时间复杂度 分析的文章：
网友评论