03、复杂度分析：如何分析、统计算法的执行效率和资源消...

东方耀

03、复杂度分析：如何分析、统计算法的执行效率和资源消耗？


只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而且，我个人认为，复
杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。
大 O 复杂度表示法
算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，
用“肉眼”得到一段代码的执行时间呢？
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执
行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time
complexity），简称时间复杂度。
时间复杂度分析：
1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的
变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影
响。
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几种常见时间复杂度实例分析
虽然代码千差万别，但是常见的复杂度量级并不多。我稍微总结了一下，这些复杂度量级几乎涵
盖了你今后可以接触的所有代码的复杂度量级。

1. <font face="微软雅黑" size="6">int cal(int m, int n) {
   
2. int sum_1 = 0;
   
3. int i = 1;
   
4. for (; i < m; ++i) {
   
5. sum_1 = sum_1 + i;
   
6. }
   
7. int sum_2 = 0;
   
8. int j = 1;
   
9. for (; j < n; ++j) {
   
10. sum_2 = sum_2 + j;
    
11. }
    
12. return sum_1 + sum_2;
    
13. }</font>

复制代码

我们无法事先评估 m 和 n 谁的量级大，所以
我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时
间复杂度就是 O(m+n)。



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


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


越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从
低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n )

总结
一、什么是复杂度分析？
1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。
二、为什么要进行复杂度分析？
1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特
点。
2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。
三、如何进行复杂度分析？
1.大O表示法
1）来源
算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行
总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
2）特点
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以
常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽
略这些项。
2.复杂度分析法则
1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相
加。
四、常用的复杂度级别？
多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包
括，
O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)
（平方阶）、O(n^3)（立方阶）
非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包
括，
O(2^n)（指数阶）、O(n!)（阶乘阶）
五、如何掌握好复杂度分析方法？
复杂度分析关键在于多练，所谓孰能生巧。