大O 如何计算代码时间复杂度和空间复杂度

先说时间复杂度：

时间复杂度表示代码执行时间与数据规模之间的增长关系。
时间复杂度怎么计算，以for循环为例，详细计算一下代码执行时间复杂度

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

在以上代码中，假定行2执行时间为1个unitTime，行3执行时间为n个unitTime，行4，5执行时间为2×n×n个unitTime，行8执行时间为1个unitTime，因此T(n)=2×unitTime+n×unitTime+2×n×n×unitTime=(2+n+2n²)unitTime。
这里有个规律：代码执行时间T(n)与代码执行次数n成正比。那么将此规律抽象为公式就是：T(n)=O(f(n))；T(n)代表代码执行时间，f(n)代表代码执行次数(2+n+2n²)；O表示正相关系数。至此大O诞生了！
我们使用大O表示复杂度，表示的是一种变化趋势，因此在n足够大的时候，f(n)中的常量，系数，低阶都可以被忽略，因此上面代码的复杂度就可以简化成：T(n)=O(n²)；

接下来总结三个实用方法来计算时间复杂度：

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

常见的时间复杂度量级（O(n!)和O(2^n)不在讨论范围内）

1. 常量阶O(1)
   一般情况下，代码中没有循环语句、递归语句，那么无论有多少行代码，都认定这段代码的时间复杂度为O(1)。
2. 对数阶O(logn)
   以如下代码为例：

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

这段代码的执行次数为log₂n，那么这段代码的时间复杂度就是O(log₂n)。底数2忽略，就是O(logn)。
那么为什么可以忽略底数呢？我们来看运算，假设有个底数为3的对数阶复杂度O(log₃n)，log₃n = log₃2 * log₂n，因此O(log₃n)=O(log₃2 * log₂n)，log₃2是常量，因此我们大致可以认为O(log₃n)=O(log₂n)，所以在计算时间复杂度的时候忽略底数完全没问题哦~

3. 线性阶O(n)

   function foo(n){
     let result;
     for(let i = 0; i < n; i++){
       result += i;
     }
   }
   

4. 线性对数阶O(nlogn)

   function foo(n){
     for(let i = 0; i < n; i++){
       let j = 1;
       while(j < n){
         j = j * 2;
       }
     }
   }
   

5. 平方阶O(n²)、3次方阶O(n³)...

   function foo(n){
     let result;
     for(let i = 0; i < n; i++){
       for(let j = 0; j < n; j++){
         result += i + j;
       }
     }
   }
   

6. 假设代码的复杂度由两个数据的规模来决定，那就有了这样的复杂度O(m+n)，O(m*n)

   function foo(m, n){
     let sum1, sum2;
     for(let i = 0; i < m; i++){
       sum1 += i;
     }
     for(let j = 0; j < n; j++){
       sum2 += j
     }
     return sum1 + sum2;
   }
   

再说空间复杂度

空间复杂度表示代码存储空间与数据规模之间的增长关系。
常见的空间复杂度O(1)、O(n)、O(n²)

function foo(n){
  let arr = [];
  for(let i = 0; i < n; i++){
    arr.push(i);
  }
}

以上代码的空间复杂度就是O(n)。