教练，我也想学复杂度分析

教练.jpeg

为什么想学?

• 如果你是一名业务开发工程师，你可能要说，我整天就是做数据库CRUD（增删改查）又或者你像我一样是个前端仔，整日最常用的命令就是npm run dev，哪里用得到数据结构和算法啊？那还有必要学习复杂度分析吗？
• 是的，对于大部分开发来说，网上的现有框架已经足够我们平时的开发了,很多现成的框架，封装使用方便，拿来就用，还不用太担心性能的问题。而我们已经很少需要自己实现数据结构和算法。
• 不需要自己实现，并不代表什么都不需要了解。如果不知道这些类库背后的原理，不懂得时间、空间复杂度分析，你如何能用好、用对它们？调用了某个函数之后，你又该如何评估代码的性能和资源的消耗呢？而数据结构和算法学习的精髓就是复杂度分析

为什么需要复杂度分析？

• 之前的我通过代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？
  1. 测试结果依赖测试环境
     测试环境中硬件的不同会对测试结果有很大的影响。比如，用不同的cpu处理器 i9处理器上的代码显然会比i3处理器上的代码运行的快。
  2. 测试结果受数据规模的影响很大。比如测试数据规模太小，测试结果可能无法真实地反应算法的性能。
• 我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是时间、空间复杂度分析方法。

大O复杂度表示法

算法的执行效率，其实就是算法代码执行的时间。如何在不运行代码的情况下，来评估一段代码的执行时间呢？

1. 求1,2,3…n的累加和，那么段这代码的执行时间又是多少呢。

   var Sum = function(n) {
       let result = 0
       for(let i= 0;i<n;i++){
           result = result+i
       }
       return result
   };
   

   可以看到每一行的代码都执行着类似的操作：读取-运算-记录。在这里粗略估计，就可以假设每行代码执行的时间都一样，为n_time。

   第2行代码需要1个为n_time的执行时间，第3,4行都运行了n遍，所以需要2nn_time的执行时间，所以这段代码总的执行时间就是(2n+1)n_time。

2. var Sum = function(n) {
           let result = 0
           for(let i= 0;i<n;i++){
                for(let j= 1;j<n;j++){
                   result = result+i*j
                }
           }
           return result
       };
   

   我们依旧假设每个语句的执行时间是n_time。那这段代码的总执行时间T(n)是多少呢？
   第2行代码，每行都需要1个n_time的执行时间，第3行代码循环执行了n遍，需要n * n_time的执行时间，第4、5行代码循环执行了n²遍，所以需
   要2n² * n_time的执行时间。所以，整段代码总的执行时间T(n) = (2n²+n+1)*n_time。

   通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间T(n)与每行代码的执行次数n成正比。
   我们可以把这个规律总结成一个公式。

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

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

   当n很大,甚至趋近于∞时。在公式中的低阶、常量、系数三部分并不能影响他的趋势，所以都可以忽略。我们只需要记录一个最大量级就可以，如果用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n²)。

时间复杂度分析

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

   大O这种复杂度表示方法表示一种变化趋势。所以，我
   们在分析一个算法、一段代码的时间复杂度的时候，也和大O这种复杂度一样只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

   还是上文的代码，这次我们来分析他的时间复杂度

   var Sum = function(n) {
       let result = 0
       for(let i= 0;i<n;i++){
           result = result+i
       }
       return result
   };
   

   其中第2行代码是常量级的执行时间，只是声明了一个变量与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第3、4行代码，这两行代码被执行了n次，所以总的时间复杂度就是O(n)。

2. 总复杂度等于循环次数最多的那段复杂度。加法法则

   var Sum = function(n) {
       let sum1 = 0
       for(let i = 0;i<1000;i++){
           sum1 = sum1+i
       }
       let sum2 = 0
       for(let j= 0;j<n;j++){
           sum2 = sum2+j
       }
       let sum3 = 0
       for(let k= 1;k<n;k++){
           for(let m = 0;m<n;m++){
               sum3 = sum3+k*m
           }
       }
       return sum1+sum2+sum3
   }
   

   这个代码分为三部分，分别是求sum1、sum2、sum3。可以分别分析每一部分的时间复杂度，然后取一个量级最大的作为整段代码的复杂度。

   第一段的时间复杂度是多少呢？这段代码循环执行了1000次，所以是一个常量的执行时间，跟n的规模无关。因此无论这个这段代码循环了多少次只要是一个已知的数与n无关那么当n趋向∞时就可以忽略。因为它本身对算法执行效率与数据规模增长的趋势并没有影响。

   第二段，第三段代码的时间复杂度分别是O(n)和O(n²)综合这三段代码的时间复杂度，取其中最大的值。整段代码的时间复杂度就为O(n²)。

   抽象成公式T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))

3. 遇到嵌套的 for 循环的时，时间复杂度呢就是内外循环的乘积。乘法法则

```
var Sum = function(n) {
    let result = 0
    let func =  function(n) {
        let func_result = 0
        for(let j= 1;j<n;j++){
            func_result = func_result +j
        }
        return func_result
   }
    for(let i = 1;i<n;i++){
        result = result+func(i)
    }
    return result
} 
```
如果func()函数只是一个普通的操作，那第10～12行的时间复杂度就是，T1(n) = O(n)。但func()函数本身不是一个简单的操作，而其本身的时间复杂度是T2(n) =
O(n)，所以，整个Sum()函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n²)。

抽象成公式 **T(n)=T1(n)✖️T2(n)=O(f(n)✖ g(n))** 

几种常见时间复杂度分析

对于复杂度量级可以分为以下两类多项式量级和非多项式量级

• 多项式量级

  1. O(1)
     通常被称为常量阶，他时间复杂度的一种表示方法，并不是指只执行了一行代码。即便有多行，它的时间复杂度也是O(1),一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
  2. ** O(n)** 线性阶
  3. ** O(n²)...O(nᵏ)** 线性阶
  4. ** O(logn)、O(nlogn)**
     对数阶,线性对数阶时间复杂度非常常见，例如

     var Sum = function(n) {
         let i=1
         while (i <= n) {
             i = i * 2;
         }
         return i
     }
     

  根据我们前面讲的复杂度分析方法，第4行代码是循环执行次数最多的。所以，我们只要算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。
  变量i的值从1开始取，每循环一次就乘以2。当大于n时，循环结束。而i的取值就是一个等比数列

  2⁰ 2¹ 2² 2³ ...... 2ˣ = n
  

  通过2x=n求解x可以算出x=log2ⁿ，所以，这段代码的时间复杂度就是O(log2ⁿ)

  而实际上，不管是以2为底、以3为底，还是以10为底，因为对数之间可以互相转化，例如log3ⁿ = log3² *log2ⁿ 所以O(log3ⁿ) = O(C * log2ⁿ)因为C是个常量我们又可以像在大O复杂度中一样将它忽略掉因此可以把所有对数阶的时间复杂度都记为O(logn)。

  而如果一段代码的时间复杂度是O(logn)，我们循环执行n遍，时间复杂度就是O(nlogn)了。

  3. ** O(n)**

• 非多项式量级

  1. O(2ⁿ)和O(n!)。指数阶，阶层阶

空间复杂度分析

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

var Sum = function(n) {
    let result = []
    for(let i= 0;i<n;i++){
        result[i] = i 
    }
    return result
};

跟时间复杂度分析一样，我们可以看到，第2行代码中，我们声明了存储变量result，整段代码的空间复杂度就是O(n)。
我们常见的空间复杂度就是O(1)、O(n)、O(n²)，

image

最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度

• 是什么？
  1. 最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
  2. 最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
  3. 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。

• 为什么要引入这几个概念？
  1. 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度。
  2. 代码复杂度在不同情况下出现量级差别时才需要区别这几种复杂度。大多数情况下，是不需要区别分析它们的。

写在最后

image

渐进时间，空间复杂度分析为我们提供了一个很好的理论分析的方向，他能够让我们对我们的程序或算法有一个大致的认识，复杂度分析能让我们对不同的算法有了一个“效率”上的感性认识。

渐进式时间，空间复杂度分析仅仅只是一个理论模型，只能大概的分析，不能直接断定就觉得O(logn)的算法一定优于O(n)

所以在实际开发中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，而通过文中提供的粗略的分析模型，也不会浪费太多时间，重点在于要具有这种复杂度分析的思维。