数据结构与算法之美复杂度分析(上)

向右看齐 2023-09-28 12:38 116阅读 0赞

####  ####

*  前言
 *  为什么需要复杂度分析
 *  大O复杂度表示法
 *  如何进行复杂度分析
 *  几种常见时间复杂度
 *  空间复杂度

文章是观看王争老师的数据结构与算法之美所写  
![在这里插入图片描述][a6a68ce24d6f4270b3aeb52882596f06.png]

## 前言 ##

数据结构和算法本身是为了解决快和省的问题，我们希望代码运行快，并且希望节省存储空间，所以执行效率是一个很重要的考量指标，接下来要讲的是时间复杂度和空间复杂度

## 为什么需要复杂度分析 ##

我们可以通过把代码跑一遍，然后通过统计，监控等得到算法执行事件和占用的内存空间大小，这种方法是事后统计法，有很大的局限性:

*  测试结果很依赖测试环境
    
     *  同样的代码在不同的机器执行速度可能不一样
 *  测试结果受数据规模的影响很大
    
     *  比如排序

所以，我们需要用一个不需要具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法，也就是时间，空间复杂度分析方法。

## 大O复杂度表示法 ##

int cal(int n) {
        
       int sum = 0;
       int i = 1;
       for (; i <= n; ++i) {
        
         sum = sum + i;
       }
       return sum;
     }

假设每行代码执行的时间都是一样，为unit\_time时间，那么总的执行时间就是(2n+2)unit\_time,所有代码的执行时间T(n)和每行代码的执行次数f(n)成正比。

我们可以把这个规律总结成一个公式。注意，大 O 就要登场了！  
![在这里插入图片描述][bc8cbb8e6aa74e3e85e95a3ff85ac205.png]

*  T(n)表示代码的执行时间，n表示数据规模大小
 *  f(n)表示每行代码执行的次数总和
 *  O表示代码的执行时间T(n)和f(n)成正比
 *  上面所说的例子T(n)=O(2n+2),这就是大O时间复杂度表示法
 *  大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

## 如何进行复杂度分析 ##

1.  只关注循环执行次数最多的一段代码
2.  加法法则：总复杂度等于量级最大的那段代码的复杂度
3.  乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

## 几种常见时间复杂度 ##

![在这里插入图片描述][bc284c0642984557a828514f43a46f78.png]

*  只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。

## 空间复杂度 ##

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

![在这里插入图片描述][b271c67257044e98b12b1ac1d4c43df8.png]

[a6a68ce24d6f4270b3aeb52882596f06.png]: https://img-blog.csdnimg.cn/a6a68ce24d6f4270b3aeb52882596f06.png
[bc8cbb8e6aa74e3e85e95a3ff85ac205.png]: https://img-blog.csdnimg.cn/bc8cbb8e6aa74e3e85e95a3ff85ac205.png
[bc284c0642984557a828514f43a46f78.png]: https://img-blog.csdnimg.cn/bc284c0642984557a828514f43a46f78.png
[b271c67257044e98b12b1ac1d4c43df8.png]: https://img-blog.csdnimg.cn/b271c67257044e98b12b1ac1d4c43df8.png