大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²)；

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

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

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

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

对数阶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)，所以在计算时间复杂度的时候忽略底数完全没问题哦~

线性阶O(n)

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

线性对数阶O(nlogn)

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

平方阶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;
    }
  }
}

假设代码的复杂度由两个数据的规模来决定，那就有了这样的复杂度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)。

最后编辑于：2020.10.14 11:02:14