时间复杂度、空间复杂度以及分析方法

在学习数据结构与算法的时候，总不免提到时间复杂度以及空间复杂度这两个概念，以及每次对所写代码进行的复杂度分析等，最近这段时间学习数据结构与算法时对这两个概念的理解比之前好些了，这篇文章记录下最基础的概念以及常见的时间/空间复杂度。

时间复杂度

先说下时间复杂度：描述一个算法执行时间与数据规模的增长关系，通常用 T(n) = O(f(n)) 来表示，这里的 n 表示数据的规模，f(n) 每行代码执行的次数总和。这里重点在于增长关系这几个字，一个算法的时间复杂度，通常只需要考虑 n 的增长规模，这里的 n 指的是每段代码的执行次数，所以时间复杂度大多都只看循环、递归来分析，而与那些常数、系数等无关。举个例子：

function calc(n){
  var sum = 0;
  var i = 1;
  for (; i < n; i++ ){
    sum += i;
  }
  return sum;
}

这段代码可以累加从 0 到 n 的和，我们这样对它进行分析：第 2、3 行代码需要执行一次，第 4、5 行需要执行 n 次，总的就是 2n 次，所以它的时间复杂度为 O(2n + 2)，但是因为系数、常数这些对 n 的增长规模没有影响，不需要考虑，可以忽略，如果是 n² 那就有影响了，都已经到平方阶了。所以这样看其时间复杂度为 O(n) 。
类似于这样的代码不用分析，时间复杂度都是常量级的 O(1)，因为它并没有体现出 n 的增长规模关系，就算代码在多时间复杂度也是一样的，换句话说，一段代码里没有循环啊、递归等语句，通常时间复杂度都是 O(1) 。再下面在看下这段代码：

function(n){
  var sum = 0;
  for(var i = 1; i <= n; i++){
    for(var j = 1; j <= n; j++){
      sum += i*j;
    }
  }
  return sum;
}

像这种嵌套了两层 for 循环的代码，两行代码分别执行了 n 遍，并且是嵌套，时间复杂度就是 O(n²)。

分析小技巧

1. 如果没有循环或递归，都是常量级的代码，时间复杂度就是 O(1)
2. 只关注循环次数最多的一段代码，它的量级就可作为整段代码的时间复杂度
3. 如果是 for 循环嵌套的代码，采用乘法计算其内外复杂度；如果是一个函数里有多段代码，则分析出每一段代码的时间复杂度，在将它们相加，最后去掉系数以及常数，取最大量级的作为整段代码的时间复杂度。例如，O(2n²+n+2) 则简化为 O(n²)

空间复杂度

类比时间复杂度，空间复杂度的概念在几个字上不一样，完整表述为:描述一个算法占用空间与数据规模的增长关系。如下代码：

function print(n){
  var i = 0;
  var arr = new Array(n);
  for(i;i<n;i++){
    arr[i] = i * i; 
  }
}

同样的，第二行代码申请了存储空间 i，但它是常量阶的，跟数据的增长规模没有关系，所以不用理；第三行代码申请了一个容量为 n 的数组，剩下的代码都没有涉及到占用空间了，所以整段代码的空间复杂度为 O(n) 。常见的空间复杂度不多，就 O(1)、O(n)、O(n²) 这几个，其余对数阶的那些一般很少应用到。

常见的复杂度

常见的复杂度从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)