极客时间-数据结构笔记03

• 为什么需要复杂度分析
• 大$O$复杂度表示法
• 时间复杂度分析
• 常见时间复杂度分析
• 空间复杂度分析
• 课后思考

---

为什么需要复杂度分析

通过统计和监控代码可以得到算法的执行时间和占用内存，这种方法叫事后统计，这种方法有很大的局限性：

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

我们需要一个不用具体的测试数据测试就可以粗略估计算法执行效率的方法。

大O复杂度表示法

代码的执行都可以看出类似的操作：读数据-运算-写数据，所有代码的执行时间T(n)与每行代码的执行时间成正比。

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

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

在采用大$O$标记复杂度的时候，可以忽略系数，即$O(Cf(n)) = O(f(n))$

时间复杂度分析

如何分析一段代码的时间复杂度？以下是三个比较实用的方法：

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

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

   如果T1(n)=O(f(n)), T2(n)=O(g(n))，那么T(n)=O(max(f(n), g(n)))

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

   如果T1(n)=O(f(n)), T2(n)=O(g(n))，那么T(n)=O(f(n) * g(n))

常见时间复杂度分析

常见的时间复杂度如下

对于以上的时间复杂度，我们可以粗略分为两类：多项式量级和非多项式量级，非多项式量级只有两个：$O(2^n)$和$O(n!)$

我们主要来看集中常见的多项式时间复杂度

1. $O(1)$

   只要算法中不存在循环语句、递归语句，即使有成百上千行代码，其时间复杂度也是O(1)​

2. $O(logn)$、$O(nlogn)$

   $O(nlogn)$是一种非常常见的算法时间复杂度，比如归并排序、快速排序等

3. $O(m+n)$、$O(m*n)$

   代码的复杂度由两个数据的规模决定

空间复杂度分析

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

常见的空间复杂度就是$O(1)$、$O(n)$、$O(n^2)$，像$O(logn)$、$O(nlogn)$这样的对数阶复杂度平时用不到，空间复杂度分析比时间复杂度分析要简单很多。

课后思考

项目之前都会有性能测试，那代码的时间复杂度、空间复杂度是否多此一举？

时间复杂度、空间复杂度为我们提供了一个很好的理论分析的方向，是宿主平台无关的，能对不同的算法“效率”有一个感性的认识；但是实际上在不同的宿主环境，不同的数据集，真正的性能会不同。所以两者是相辅相成的，但是在编程中时刻关心时间、空间复杂度更有助于产出效率高的程序。