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

Posted on | In

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半

什么是复杂度分析

  1. 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
  2. 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
  3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
  4. 复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

为什么要进行复杂度分析？

  1. 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
  2. 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

如何进行复杂度分析？

大O表示法

算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势 –> 渐进时间复杂度 简称时间复杂度

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码
    1
    2
    3
    4
    5
    6
    7
    8
    int cal(int n) {
      int sum = 0;
      int i = 1;
      for (; i <= n; ++i) {
        sum = sum + i;
      }
      return sum;
    }

时间复杂度 0(n)

  1. 加法法则：总复杂度等于量级最大的那段代码的复杂度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    int cal(int n) {
       int sum_1 = 0;
       int p = 1;
       for (; p < 100; ++p) {
         sum_1 = sum_1 + p;
       }
       
       O(1)

       int sum_2 = 0;
       int q = 1;
       for (; q < n; ++q) {
         sum_2 = sum_2 + q;
       }
       
       O(n)
     
       int sum_3 = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1; 
         for (; j <= n; ++j) {
           sum_3 = sum_3 +  i * j;
         }
       }
       
       O(`$ n^2$`)
     
       return sum_1 + sum_2 + sum_3;
     }

时间复杂度为: O(1)+O(n)+O($ n^2$) 根据规则最后的时间复杂度为 O($ n^2$)

  1. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int cal(int n) {
       int ret = 0; 
       int i = 1;
       for (; i < n; ++i) {
         ret = ret + f(i);
       } 
     } 
     O(n)
     
     int f(int n) {
      int sum = 0;
      int i = 1;
      for (; i < n; ++i) {
        sum = sum + i;
      } 
      return sum;
     }
     O(n)*O(n)

时间复杂度为：O($ n^2$)

时间复杂度分析总结

  1. 单段代码看高频：比如循环。
    2。 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
  2. 嵌套代码求乘积：比如递归、多重循环等
  3. 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

时间复杂度获得计算的结果

以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。

常用的复杂度级别？

  1. 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
    O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O($ n^2$)（平方阶）、O($ n^3$)（立方阶）
    1
    2
    3
    4
    5
    6
    7
    常见的：
    1. O(1)
    2. O(logn)、O(nlogn)
     i=1;
     while (i <= n)  {
       i = i * 2;
     }

以上的结果是
image

1
2
3
4
5
6
7
在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))

O(nlogn)--->归并排序、快速排序的时间复杂度

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

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。
  1. 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，
    O($ 2^n$)（指数阶）、O(n!)（阶乘阶）

控件复杂度

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

常见：
我们常见的空间复杂度就是 O(1)、O(n)、O($n^2$) 像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到

总结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O($n^2$)

image

来源

本文是从 王争 数据结构与算法的学习-03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？。跟着大神学习，逐渐进步