课程：《复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？》 总结

算法的一个非常重要的的考量指标是执行效率，复杂度分析就是用来衡量代码执行效率的一种方法。前面又提到复杂度分析是数据结果和算法学习的精髓。

为什么需要复杂度分析？

1. 实际的测试结果非常依赖测试环境

比如测试环境硬件配置不一样，得到的结果截然不同

2. 测试结果受数据规模的影响很大

比如排序算法，就会受实际测试数据的有序度和数据的规模影响。导致测试的结果无法反应算法的性能。

3. 可以开发阶段更好的指导代码的编写

复杂度分析可以估算代码的执行效率，从而在根据实际选择算法时起到一定的指导作用。

复杂度分析不需要具体测试数据测试，就可以大概估计算法执行效率。既快速方便，又不受测试环境的影响，所以我们需要复杂度分析。

复杂度分析包括时间复杂度分析和空间复杂度分析，那么如何进行复杂度分析呢？

大O复杂度表示法

如果我们将每行代码的执行时间看成固定的，那所有代码的执行时间 T(n) 与每行代码的执行次数成正比。我们再将每行代码的执行次数之和用f (n)表示，那就可以总结出一个公式:

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

其中n表示数据规模的大小，O代表T(n)与f(n)之间是正比关系。这就是大O时间复杂度表示法。

大O时间复杂度表示的是代码执行时间随数据规模增长的变化趋势。并不是正真的执行时间。当n很大时，公式中的低阶、常量、系数三部分对变化趋势影响不大，所以可以忽略，只记录最大量级的那个就可以了。

时间复杂度分析

三个实用的时间复杂度分析方法:

1. 单一循环看次数执行最多的

2. 如果代码只受单一数据规模n的影响，非嵌套循环相加取量级最大的

3. 如果代码受多个数据规模的影响，非嵌套循环相加取和

4. 嵌套循环内外相乘取乘积

常见的时间复杂度有：O(1)、O(logn)、O(n)、O(nlogn)、O( )。

此外还有:O(m+n)、O(m*n)，前者为复杂度有两个数据规模决定，后者则是起决定性的两个数据规模是嵌套的。

空间复杂度分析

由时间复杂度的表示意义可知，空间复杂度表示的是算法的存储空间随数据规模增长的变化趋势。

常见的空间复杂度有： O(1)、O(n)、O()。空间复杂度和时间复杂度类似，所以和数据规模n无关的相，我们都可以忽略。

时间复杂度练习：

练习一：

图一

如上图一：函数test，有一个形参n，这个函数需要执行的代码为第4行、第5行，在调用函数test的过程中，第4行n代码是将n和5做了乘法，运行次数为1次，第5行代码为返回num的值，执行次数也为1次，根据大O复杂度表示法，可知f(n)为每行代码执行次数之和，所以这段代码的时间复杂度T(n)=O(1 + 1) = O(2)，又因为时间复杂度研究的是代码执行时间随数据规模增长的趋势。可见，图一代码中每行代码的执行次数之和是一个常量，当n很大时，常量对变化趋势影响不大，所以可以忽略。这种代码执行时间为常量的时间复杂度都可以表示为O(1)。

图二

图三

再看图二、图三，虽然代码的行数变多了，但是通过分析可知，这几段代码中每行代码的执行次数之和都是常量，执行时间并不随数据规模n的增长而变化。所以他们的时间复杂度都是O(1)。

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

练习二：

图四

再看图四，分析可知第4行代码的执行次数是n次，第5行代码的执行次数也是n次，可得这段代码的时间复杂度T(n)=O(n + n)=O(2n)。我们将系数忽略，取最大两级的一个，得到T(n)=O(n)。所以这段代码的时间复杂度就是O(n)。这也验证了“单一循环看次数执行最多的行”的分析方法。

练习三：

图五

再来看一个嵌套循环，如图五，分析可知第4行代码执行次数为n，第5行代码执行次数为n x n，第6行代码的执行次数为n x n。所以根据大O复杂度表示法可得这段代码的时间复杂度为：T(n)=O(n + nxn + nxn)=O(n+2)。又知低阶、系数可以忽略，这段代码的时间复杂度为:T(n)=O()。刚好验证了“嵌套循环内外相乘取乘积”的分析方法。

练习四：

图六

如图六，根据单一循环看次数执行最多的行的分析方法，可知我们只要分析第5行代码或者第6行代码就可以了。代码中循环结束的条件是i>=n，但是i并不是每次递增1，i的变化是每次乘以2。假设第6行代码执行x次后循环结束，那么i的取值列出来就是, , , , ,,...，可以看出i的值为，x即为第6行代码执行的次数。也就是当>= n时循环结束。那我们就可以近似的得出第6行代码的执行次数x=，所以这段代码的时间复杂度T(n)=O()。那么当第6行代码变成i= i * 3或者i=i*10等的时候，那这段代码的时间复杂度就是O()、O()。不管是以哪个数字为底，我们都可以把这种对数阶的时间复杂度表示为O(logn)。所以图六代码的时间复杂度为T(n)=O(logn)。

练习五：

图7

我们已经知道test函数这段代码的时间复杂度为O(logn)，那test2这段代码是将test代码段嵌套在了一个for循环中，根据“嵌套循环内外相乘取乘积”的分析方法，可知for循环中test函数的执行次数为n,所以外部循环代码段的时间复杂度为O(n)，又因为内部循环代码段的时间复杂度，也就是test代码段的时间复杂度为：O(logn)，可得到test2代码段的时间复杂度T(n)=O(n)*O(logn)=O(nlogn)。

练习六：

图8

前面的代码段都是只有一个参数n，图8中的test函数有两个形参m和n，再看函数体，第3、4行代码的执行次数受m的影响，第5、6行代码的执行次数受n的影响。即图8代码段的每行代码的执行次数之和受到了m和n两个数据规模的影响。这种情况下，m和n都不能确定是多少，所以都不能忽略。我们分析可知，第3、4行代码的时间复杂度T1(m)=O(m)，第5、6行代码的时间复杂度T2(n)=O(n)，所以根据“如果代码受多个数据规模的影响，非嵌套循环相加取和”的分析方法可得，这段代码的时间复杂度为：T(m)+T(n)=O(m)+O(n)=O(m+n)。

练习七：

图9

图9代码段是一个嵌套循环，我们可以先将第4、5行代码段看成是一个单一循环，很容易可以得到它的时间复杂度T(n)=O(n)，再看第3行代码，这是外部循环部分，这行代码的执行次数受m的影响，从而得到外部循环代码段的时间复杂度为T(m)=O(m)，根据“嵌套循环内外相乘取乘积”的分析方法，可得test代码段的时间复杂度为：T(m)*T(n)=O(m)*O(n)=O(m*n)。

空间复杂度练习：

练习一：

图10

图10中，第3行代码中，我们申请了一块空间a来存放数字4，第4行代码中我们又申请了一块空间sum来存放a+n的和。第5行代码并没有申请空间，只是返回了sum的值。由于空间复杂度表示的是算法的存储空间随数据规模增长的变化趋势，而经过我们分析，不管n的数据规模如何变化，这段代码永远只是申请了a和sum两块空间，并没有对存储空的的变化趋势造成影响，可见是常量阶的，所以这段代码的空间复杂度为：O(1)。

图11

再来看图11，第3行代码中创建了一个list对象num_list，第4、5行代码中是循环三次，每次讲i*n的值存放到num_list对象中。由于num_list是一个可变对象，每存入一个数据就需要申请一块存储空间。但是由于第4行代码中，循环的次数是固定的3次，所以不管数据规模n如何变化，代码中只是申请了三次存储空间。也没有对存储空间的变化趋势造成影响，所以它的空间复杂度也是常量阶的，所以也是O(1)。

练习二：

图12

图12和图11不同之处在于第4、5行代码的执行次数受n的数据规模的影响，我们知道num_list对象是一个列表，每放入一个数据都会申请一块空间存储，如果放入n个数据，那就要申请n块空间存储，所以这段代码的申请存储空间的次数或总量，会受到n的影响，所以可以得出这段代码的空间复杂度为：O(n)。

图13

图13是在图12代码段的举出上又嵌套的一层循环，更具“嵌套循环内外相乘取乘积”的分析方法，可知，图13这段代码的空间复杂度为：O(n*n)=O()。

以上就是我对本节课程的理解，当然例子都是写的简单的例子。王争老师提到“复杂度分析并不难，关键在于多练。”，我在学习的时候，就是先听讲几遍，在动手写一下代码，试着分析一下复杂度。然后再和课程讲的核对下，看是不是一样，然后再多听几遍。这样使我印象更深刻。慢是慢了些，但相信对我而言应该是不错的学习方法。

以上可能有些理解的不到位，或是表达的不准，欢迎大家指正，帮助我更好的理解。

上一篇：《数据结构和算法之美》学习笔记 Day 1

下一篇：《数据结构和算法之美》学习笔记 Day 3