day-1-复杂度分析（上）

一、为什么需要复杂度分析

1.1 事后统计法的局限性

• 测试结果非常依赖测试环境
• 测试结果受数据规模的影响很大

1.2 大 O 复杂度表示法

大 O 时间复杂度表示法表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。

二、时间复杂度分析方法

2.1 只关注循环执行次数最多的一段代码

2.2 加法法则：总复杂度等于量级最大的那段代码的复杂度

2.3 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

三、几种常见时间复杂度分析

3.1 非多项式量级

非多项式量级只有两个：O(2的n次方)和O(n!)

3.2 多项式量级

a) O(1)

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)。

b) O(logn)、O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。
归并排序、快速排序的时间复杂度都是O(nlogn)。

c) O(m + n)、O(m * n)

T1(m) + T2(n) = O(f(m) + g(n))
T1(m) * T2(n) = O(f(m) * f(n))

四、空间复杂度分析

空间复杂度全称为渐进空间复杂度，表示算法的存储空间与规模之间的增长关系。

五、小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。