数据结构与算法：1.复杂度分析

青旅半醒 2023-07-22 05:57 43阅读 0赞

# 复杂度分析： #

数据结构和算法解决的两大问题：快和省。运行快，储存省。

复杂度分析是算法学习的精髓：时间复杂度，空间复杂度。

某个十字路口没有建立立交桥时，所有车辆通过红绿灯分批次行驶通过。当大量汽车同时过路口的时候，就会分别消耗大家的时间。但建了立交桥之后，所有车辆都可以同时通过了，因为立交桥的存在，等于是消耗了空间资源，来换取了时间资源。

我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的**降低时间复杂度**的方法有**递归、二分法、排序算法、动态规划**等；降低空间复杂度的方法，就要围绕**数据结构**做文章了。

降低空间复杂度的核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

事后统计法有很大局限性：

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

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

例1：

1  int cal(int n) { 
    2    int sum = 0;
    3    int i = 1;
    4    for (; i <= n; ++i) { 
    5     sum = sum + i;
    6    }
    7    return sum;
    8  }

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：**读数据**\-**运算**\-**写数据**。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit\_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？

第 2、3 行代码分别需要 1 个 unit\_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n \* unit\_time 的执行时间，所以这段代码总的执行时间就是 (2n+2)\*unit\_time。可以看出来，**所有代码的执行时间 T(n) 与每行代码的执行次数成正比**。

例2：

1  int cal(int n) { 
    2    int sum = 0;
    3    int i = 1;
    4    int j = 1;
    5    for (; i <= n; ++i) { 
    6      j = 1;
    7      for (; j <= n; ++j) { 
    8        sum = sum +  i * j;
    9      }
    10    }
    11  }

第 2、3、4 行代码，每行都需要 1 个 unit\_time 的执行时间，第 5、6 行代码循环执行了 n 遍，需要 2n \* unit\_time 的执行时间，第 7、8 行代码循环执行了 n²遍，所以需要 2n² \* unit\_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n²+2n+3) \* unit\_time 。

尽管我们不知道 unit\_time 的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，**所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比**。

公式：  
 T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))  
其中，

*  T(n) 表示代码执行的时间；
 *  n 表示数据规模的大小；
 *  f(n) 表示每行代码执行的次数总和。
 *  O表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

例1即T(n) = O(2n+2)，例2即 T(n) = O(2n²+2n+3)。这就是**大 O 时间复杂度表示法**。其并不具体表示代码真正的执行时间，而是表示**代码执行时间随数据规模增长的变化趋势**，所以，也叫作**渐进时间复杂度**（asymptotic time complexity），简称**时间复杂度**。

当 n --> +∞，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，就可以记为：T(n) = O(n)； T(n) = O(n²)。

#### 时间复杂度分析的三个方法： ####

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

大 O 这种复杂度表示方法只是表示一种变化趋势。忽略公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，**分析算法时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了**。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

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

int cal(int n) { 
       int sum_1 = 0;
       int p = 1;
       for (; p < 100; ++p) { 
         sum_1 = sum_1 + p;
       }
     
       int sum_2 = 0;
       int q = 1;
       for (; q < n; ++q) { 
         sum_2 = sum_2 + q;
       }
     
       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;
         }
       }
     
       return sum_1 + sum_2 + sum_3;
     }

sum\_1时间复杂度是个常量，理应被忽略，与规模n无关。强调一下，即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以**不管常量的执行时间多大，我们都可以忽略掉**。因为它本身对增长趋势并没有影响。

sum\_2是O(n)，sum\_3是O(n²)。综合这三段代码的时间复杂度，我们取其中最大的量级，即O(n²)。  
 T ( n ) = T 1 ( n ) + T 2 ( n ) = m a x ( O ( f ( n ) ) , O ( g ( n ) ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) . T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))). T(n)=T1(n)\+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n))).

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

T ( n ) = T 1 ( n ) ∗ T 2 ( n ) = O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) T(n)=T1(n)\*T2(n)=O(f(n))\*O(g(n))=O(f(n)\*g(n)) T(n)=T1(n)∗T2(n)=O(f(n))∗O(g(n))=O(f(n)∗g(n))

也就是说，假设 T1(n) = O(n)，T2(n) = O(n²)，则 T1(n) \* T2(n) = O(n³)。

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

fun()为T1(n) = O(n)，而cal()本身有for循环即T2(n) = O(n))，for循环中又调用了fun(),即T(n) = T1(n) \* T2(n) = O(n\*n) = O(n²)。

复杂度分析这个东西关键在于“熟练”。

##### 常见时间复杂度： #####

递增顺序依次是：

多项式量级：常量阶O(1)，对数阶O(logn)，线性阶O(n)，线性对数阶O(nlogn)，K方阶O(n^k)

非多项式量级：指数阶O(2ⁿ)，阶乘阶O(n!)

注：非多项式量级的算法问题叫作**NP**（Non-Deterministic Polynomial，非确定多项式）**问题**。当数据规模 n 越来越大时，其执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法，理应避免。

![(C:\\Users\\lagou\\Desktop\\8d5d86ecb45043edb99825cebccd5632.png)\]][C_Users_lagou_Desktop_8d5d86ecb45043edb99825cebccd5632.png]

源自：**[Big-O Complexity Chart][]**

###### O(1) ######

常量级时间复杂度的表示方法，并不是指只执行了一行代码，即便执行了三行，也只能是O(1)；只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，**一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)**。

###### O(logn)、O(nlogn) ######

对数阶 最常见，也是最难分析的一种。

i=1;
     while (i <= n)  { 
       i = i * 2;
     }

代码执行次数 即i<=n截止，`i=1，2，4，8，16，32……2^k……2^x=n`;

求解执行次数就是 求解 2^x = n 中的x；x=log₂n，T(n)=O(log₂n)；

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？

> 我们知道，对数之间是可以互相转换的，log₃n 就等于 log₃2 \* log₂n，所以 O(log₃n) = O(C \* log₂n)，其中 C=log₃2 是一个常量。基于我们前面的一个理论：**在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))**。所以，O(log₂n) 就等于 O(log₃n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

###### O(m+n)、O(m\*n) ######

int cal(int m, int n) { 
      int sum_1 = 0;
      int i = 1;
      for (; i < m; ++i) { 
        sum_1 = sum_1 + i;
      }
     
      int sum_2 = 0;
      int j = 1;
      for (; j < n; ++j) { 
        sum_2 = sum_2 + j;
      }
     
      return sum_1 + sum_2;
    }

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

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)\*T2(n) = O(f(m) \* f(n))。

###### 数据结构操作的复杂性 ######

<table> 
 <thead> 
  <tr> 
   <th>数据结构</th> 
   <th>连接</th> 
   <th>查找</th> 
   <th>插入</th> 
   <th>删除</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>数组</strong></td> 
   <td>1</td> 
   <td>n</td> 
   <td>n</td> 
   <td>n</td> 
  </tr> 
  <tr> 
   <td><strong>栈</strong></td> 
   <td>n</td> 
   <td>n</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td><strong>队列</strong></td> 
   <td>n</td> 
   <td>n</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td><strong>链表</strong></td> 
   <td>n</td> 
   <td>n</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td><strong>哈希表</strong></td> 
   <td>-</td> 
   <td>n</td> 
   <td>n</td> 
   <td>n</td> 
  </tr> 
  <tr> 
   <td><strong>二分查找树</strong></td> 
   <td>n</td> 
   <td>n</td> 
   <td>n</td> 
   <td>n</td> 
  </tr> 
  <tr> 
   <td><strong>B树</strong></td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
  </tr> 
  <tr> 
   <td><strong>红黑树</strong></td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
  </tr> 
  <tr> 
   <td><strong>AVL树</strong></td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
   <td>log(n)</td> 
  </tr> 
 </tbody> 
</table>

数组排序算法复杂性：

<table> 
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>最优</th> 
   <th>平均</th> 
   <th>最坏</th> 
   <th>内存</th> 
   <th>稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>冒泡排序</strong></td> 
   <td>n</td> 
   <td>n²</td> 
   <td>n²</td> 
   <td>1</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td><strong>插入排序</strong></td> 
   <td>n</td> 
   <td>n²</td> 
   <td>n²</td> 
   <td>1</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td><strong>选择排序</strong></td> 
   <td>n²</td> 
   <td>n²</td> 
   <td>n²</td> 
   <td>1</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td><strong>堆排序</strong></td> 
   <td>n log(n)</td> 
   <td>n log(n)</td> 
   <td>n log(n)</td> 
   <td>1</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td><strong>归并排序</strong></td> 
   <td>n log(n)</td> 
   <td>n log(n)</td> 
   <td>n log(n)</td> 
   <td>n</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td><strong>快速排序</strong></td> 
   <td>n log(n)</td> 
   <td>n log(n)</td> 
   <td>n²</td> 
   <td>log(n)</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td><strong>希尔排序</strong></td> 
   <td>n log(n)</td> 
   <td>取决于差距序列</td> 
   <td>n (log(n))²</td> 
   <td>1</td> 
   <td>No</td> 
  </tr> 
 </tbody> 
</table>

#### 空间复杂度 ####

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

1 void print(int n) { 
    2   int i = 0;
    3   int[] a = new int[n];
    4   for (i; i <n; ++i) { 
    5     a[i] = i * i;
    6   }
     
      for (i = n-1; i >= 0; --i) { 
        print out a[i]
      }
     }

第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。

我们常见的空间复杂度就是 O(1)、O(n)、O(n² )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握这些内容已经足够了。

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

#### 一、复杂度分析的4个概念： ####

*  1.最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
 *  2.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
 *  3.平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
 *  4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
    
    分别解释四种情况：
    
    长度为n的数组中查找x的下标，来返回，找不到则返回-1；
    
        // n 表示数组 array 的长度
        int find(int[] array, int n, int x) { 
          int i = 0;
          int pos = -1;
          for (; i < n; ++i) { 
            if (array[i] == x) { 
               pos = i;
               //break;//TODO:找到即跳出
            }
          }
          return pos;
        }
    
    1.如果不加break的话，O(n)
    
    2.加上break后，或许array\[0\]就是x，复杂度O(1)【最好情况】，只有数组不包含x时，才循环到n次【最差情况】。
    
    最好情况 和 最坏情况 都是极端情况。引入一个概念：平均时间复杂度。
    
    要查找的变量 x 在数组中的位置，有 n+1 种情况：**在数组的 0～n-1 位置中**和**不在数组中**。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：  
     1 + 2 + 3 + … … + n + n n + 1 = n ( n + 3 ) 2 ( n + 1 ) \\frac \{1+2+3+……+n+n\}\{n+1\}=\\frac\{n(n+3)\}\{2(n+1)\} n\+11\+2\+3\+……\+n\+n=2(n\+1)n(n\+3)  
    省略掉系数、低阶、常量，简化之后，得到的平均时间复杂度就是 O(n)。
    
    这个结论虽然是正确的，但是计算过程稍微有点儿问题。究竟是什么问题呢？我们刚讲的这 n+1 种情况，出现的概率并不是一样的。
    
    我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便你理解，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。
    
    因此，前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：  
     1 ∗ 1 2 n + 2 ∗ 1 2 n + 3 ∗ 1 2 n + … + n ∗ 1 2 n + n ∗ 1 2 = 3 n + 1 4 1\*\\frac\{1\}\{2n\}+2\*\\frac\{1\}\{2n\}+3\*\\frac\{1\}\{2n\}+…+n\*\\frac\{1\}\{2n\}+n\*\\frac\{1\}\{2\}=\\frac\{3n+1\}\{4\} 1∗2n1\+2∗2n1\+3∗2n1\+…\+n∗2n1\+n∗21=43n\+1  
    这个值就是概率论中的**加权平均值**，也叫作**期望值**，所以平均时间复杂度的全称应该叫**加权平均时间复杂度**或者**期望时间复杂度**。
    
    去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。
    
    在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。
    
    **均摊时间复杂度**
    
    平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。
    
        // array 表示一个长度为 n 的数组
         // 代码中的 array.length 就等于 n
         int[] array = new int[n];
         int count = 0;
         
         void insert(int val) { 
            if (count == array.length) { 
               int sum = 0;
               for (int i = 0; i < array.length; ++i) { 
                  sum = sum + array[i];
               }
               array[0] = sum;
               count = 1;
            }
         
            array[count] = val;
            ++count;
         }
    
    这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。
    
    最好为O(1)，最差为O(n)。
    
    那平均时间复杂度是多少呢？答案是 O(1)。我们还是可以通过前面讲的概率论的方法来分析。
    
    假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：  
     1 ∗ 1 n + 1 + 1 ∗ 1 n + 1 + … + 1 ∗ 1 n + 1 + … + 1 ∗ 1 n + 1 + n ∗ 1 n + 1 = O ( 1 ) 1\*\\frac\{1\}\{n+1\}+1\*\\frac\{1\}\{n+1\}+…+1\*\\frac\{1\}\{n+1\}+…+1\*\\frac\{1\}\{n+1\}+n\*\\frac\{1\}\{n+1\}=O(1) 1∗n\+11\+1∗n\+11\+…\+1∗n\+11\+…\+1∗n\+11\+n∗n\+11=O(1)

其实理解平均复杂度不需这么复杂，我们可以对比 insert() 和find()的区别：

1.find() 只有在极端情况下，才为 O(1)。但 insert() 通常为 O(1)，极端情况下O(n)。

2.insert() 中O(1) 和 O(n) 出现的频率有规律，且有一定的前后时序关系，一个 O(n)之后，紧跟着 n-1 个 O(1) ，周期循环。

针对这种特殊的场景，完全不需要平均复杂度那样用概率加权平均，我们引入了一种更加简单的分析方法：**摊还分析法**，对应**均摊时间复杂度**。

如何用？每一个O(n) 紧跟 n-1 个 O(1) ，把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。该方法不常用，点到为止。

简单总结下：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

#### 二、为什么要引入这4个概念？ ####

1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。

2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

#### 三、如何分析平均、均摊时间复杂度？ ####

1.平均时间复杂度

代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。

2.均摊时间复杂度

下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。