【必备算法】基础：复杂度分析

叁歲伎倆 2022-12-12 12:30 174阅读 0赞

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

*  测试结果非常依赖测试环境
 *  测试结果受数据规模的影响很大

所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法

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

大 O 复杂度表示**代码执行时间或空间，随数据规模++的变化趋势**，也叫作渐进时间复杂度 （asymptotic time complexity），简称时间复杂度。

*  数据规模：数据的 多少 或 大小
 *  时间 / 空间
    
     *  时间：所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。即 `T(n) = O(f(n))`， 比如 `T(n) = O(2n+2)`
     *  空间：如 `new int[]`
 *  特点：公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。只需要记录一个最大量级就可以了

## 3.时间复杂度 ##

### 3.1 时间复杂度计算（重点） ###

1.  最多执行法则：在分析一个算法、一段代码的时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了
2.  加法法则：总复杂度等于量级最大的那段代码的复杂度。将这个规律抽象成公式就是：
    
        如果，T1(n)=O(f(n))，T2(n)=O(g(n))；
        那么，T(n) =T1(n) + T2(n) = max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
3.  乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。将这个规律抽象成公式就是：
    
        如果，T1(n) = O(n)，T2(n) = O(n)
        那么，T1(n) * T2(n) = O(n^2)
    
    落实到具体的代码上，可以把乘法法则看成是嵌套循环
4.  **取反法则**：O(f(n)) 也可以理解成，数据规模为 n 时代码需要执行的次数 f(n)。由于执行次数为 n 所能达到的数据规模好分析，所以我们可以先求出执行次数++与数据规模的变化规律，然后再取反
    
        O(f(数据规模为n))= O(f ^ (-1)(执行次数为n))

### 3.2 常见时间复杂度（重点） ###

时间复杂度大致可以分为以下几个量级：

<table> 
 <thead> 
  <tr> 
   <th><strong>执行次数函数</strong></th> 
   <th><strong>阶</strong></th> 
   <th><strong>非正式术语</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>12</td> 
   <td>O(1)</td> 
   <td>常数阶</td> 
  </tr> 
  <tr> 
   <td>5log2^n + 20</td> 
   <td>O(logn)</td> 
   <td>对数阶</td> 
  </tr> 
  <tr> 
   <td>2n + 3</td> 
   <td>O(n)</td> 
   <td>线性阶</td> 
  </tr> 
  <tr> 
   <td>2n + 3nlog2^2 + 19</td> 
   <td>O(nlogn)</td> 
   <td>线性对数阶</td> 
  </tr> 
  <tr> 
   <td>3n^2 + 2n + 1</td> 
   <td>O(n^2)</td> 
   <td>平方阶</td> 
  </tr> 
  <tr> 
   <td>6n^3 + 2n^2 + 3n + 4</td> 
   <td>O(n^3)</td> 
   <td>立方阶</td> 
  </tr> 
  <tr> 
   <td>2^n</td> 
   <td>O(2^n)</td> 
   <td>指数阶</td> 
  </tr> 
  <tr> 
   <td>n* (n-1) * (n-2) <em>…</em> 2 * 1</td> 
   <td>O(n!)</td> 
   <td>阶乘阶</td> 
  </tr> 
 </tbody> 
</table>

对于上面罗列的复杂度量级，我们可以粗略地分为两类，**多项式量级和非多项式量级**。其中， 非多项式量级只有两个：O(2^n) 和 O(n!)。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]  
**O(1)**

O(1)即代码执行次数不受数据规模变化影响。

int i = 8; 
    int j = 6; 
    int sum = i + j;

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

**O(logn)、O(nlogn)**

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

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。实际上，变量 i 的取值就是一个等比数列。如果把它一个一个列出来，就应该是这个样子的：2¹ 2² 2³ … 2x = n

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2 =n 求解 x 这个 问题我们想高中应该就学过了，我就不多说了。x=log n，所以，这段代码的时间复杂度就 是 O(log n)。

另外，这里还可以用上面说到底取反法则进行分析。当代码执行 n 次时，能达到的数据规模是 2^n，所以取反得时间复杂度O(logn)。

注：O(nlogn)：可以通过乘法法则得到 O(n) \* O(logn)，即外层再嵌套一层循环

for(j=1;i<arr.length;i++) {
        
    	i = arr[i]
        while (i <= n)  {
           
        	i = i * 2; 
    	}
    }

**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))。

### 3.3 涉及if的复杂度 ###

涉及到 if 的复杂度有四种：最好、最坏、平均，均摊。下面把他们分成两组来对比介绍…

**最好情况时间复杂度 & 最坏情况时间复杂度**

*  最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
 *  最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度

// n 表示数组 array 的长度 
    int find(int[] array, int n, int x) 
    {
          
        int i = 0;  
     	int pos = -1;  
     	for (; i < n; ++i) 
        {
            
        	// 最好是arr[0]就匹配到，复杂度是O(1)
        	// 最坏是arr[n-1]才匹配到，复杂度是O(n)
        	if (array[i] == x) 
            {
           
                pos = i;       
             	break;    
            }  
        }  
        return pos; 
    }

**平均情况时间复杂度 & 均摊时间复杂度**

*  平均时间复杂度：适用于 for \{ if \}，一般等于最坏情况复杂度
 *  均摊时间复杂度：适用于 if \{ for \}，一般等于最好情况复杂度

// array 表示一个长度为 n 的数组 
    int[] array = new int[n]; 
    int count = 0;
    
    // 向数组中添加元素
    void insert(int val) {
          
    	// 如果数组满了
    	// 此时就可以用到均摊复杂度。可以想到大部分情况下数组是没满的，所以均摊时间复杂度=最好时间复杂度=O(1)
        if (count == array.length) {
               
            int sum = 0; // 1.用sum来保存所有元素的和
            for (int i = 0; i < array.length; ++i) {
                  
                sum = sum + array[i];       
            }       
            array[0] = sum; // 2.在arr[O]保存sum    
            count = 1;  // 3.清空数组
        }
     	
     	// 将val插入
        array[count] = val;    
        ++count; 
    }

大部分情况下，我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。

## 4.空间复杂度 ##

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示**算法的存储空间与数据规模++的增长关系**。而我们常见的空间复杂度就是 O(1)、O(n)、O(n )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

空间复杂度 O(n) 代码示例：

void print(int n) {
          
        int i = 0; 
        int[] a = new int[n]; 
        for (i; i <n; ++i) {
           
            a[i] = i * i; 
        }
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e46da154354541ca92394b04d60b554f.png