数据结构与算法 - 时间和空间复杂度

时间复杂度

在数据结构和算法中，有两种方法来衡量时间复杂度

• 事后统计法

• 大 O 复杂度表示法

事后统计法

把代码实际跑一遍，然后分析，统计和监控算法执行的时间和占用的内存大小。但是这种方法有很大的局限性

1. 测试结果非常依赖测试环境： 测试环境的硬件不同会对结果有很大的影响，比如相同的代码在不同的处理器结果肯定不同

2. 测试结果受测试数据的规模大小的影响： 比如对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。另外，如果测试数据过小，也可能无法真是反应算法的性能，比如对于小规模的数据排序，插入排序可能反倒比快速排序要快

大 O 时间复杂度表示法

时间复杂度的分析方法：

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

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

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

常见的时间复杂度分析

复杂度的量级有可以分为 多项式量级 和 非多项式量级

• 非多项式量级：O(2^n) 和 O(n!)，非常低效的算法，执行时间会随数据的规模急剧增加

• 多项式量级：剩下的

1. O(1)

一般情况下，只要算法的代码中，不存在循环语句，递归，即使代码有很多，时间复杂度也是 O(1)

O(logn), O(nlogn)

在采用大 O 复杂度分析的情况下，可以忽略系数，比如 O(Cf(n)) = O(f(n))

O(m+n), O(m*n)

因为 m，n 两个数据规模，我们无法评估谁的规模比较大，所有我们不能省略某一个

空间复杂度

常见的空间复杂度有 O(1),O(n),O(n^2),O(logn),O(nlogn)。空间复杂度相对比较简单，而且一般使用到的都是 O(1),O(n),O(n^2)。

复杂度比较分析