day02 算法的时间与空间复杂度分析

1、为什么要学习复杂度分析？

1. 比起跑代码，统计与监控，这种事后分析方法，有很大的局限性。（依赖测试环境、收数据规模影响较大）
2. 不需要具体数据，来事前粗略估计算法执行效率的方法。

2、大O复杂度表示法

T(n) = O (f(n))

所有代码的执行时间与每行代码的执行次数成正比

并不表示真正的代码执行时间，而是表示代码执行时间随数据规模的变化趋势，也称渐进时间复杂度。简称时间复杂度

3、如何分析？

1. 只关注循环执行次数最多的一段代码
2. 减法法则 （总复杂度=量级最大那段代码的复杂度）
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: 下面下面是之前写过的一篇时间复杂度 分析的文章：

时间复杂度分析