算法复杂度

大家好，我是杨成功。

算法复杂度是区分算法性能的一个总体指标。当我们实现一个算法的时候，还要评估本次实现的性能是否过关。如何评估算法实现的性能呢？主要是从时间和空间两个方面入手。

时间方面，算法大概执行了多少次，一般执行的次数越多耗时越长，这种评价依据叫时间复杂度。

空间方面，算法执行过程中占用了多少内存，一般动态创建或修改变量会增加内存，这种评价依据叫空间复杂度。

时间复杂度

我们从一个 demo 开始，请看下面代码一共执行了多少次。

function traverse(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    console.log(arr[i]);
  }
}

首先，这一句只执行一次：

var len = arr.length;

接着是一个 for 循环，关于 for 循环的执行次数，可以记住这个规则：

• 初始化值执行一次。
• 循环体和修改值执行 n 次。
• 循环条件执行 n+1 次。

那么，将循环拆解，其执行次数如下：

var i = 0; // 1 次
i < len; // n+1 次
i++; // n 次，与循环体执行次数一样

统计该函数的执行次数，大致如下：

T(n) = 1 + 1 + (n+1) + n + n = 3n + 3

虽然详细的代码执行次数能精确表示代码执行时间，但这样计算显然过于繁琐。时间复杂度只是反映一个总体趋势，对于逐次递增/递减的循环来说，我们只需要关注指数，其他数据可以全部去掉。

将表达式 3n + 3 的系数（n）和常数（3）去掉，得出时间复杂度为：

O(n) = n
// 简写为
O(n)

这么来看，时间复杂度是可以通过肉眼来判断的。再写一个双层循环：

function traverse(arr) {
  var len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = len; j > 0; j--) {
      console.log(arr[i], arr[j - 1]);
    }
  }
}

代码中循环了两层，因此可直接推断出时间复杂度为 n * n，表示如下：

O(n) = n * n
// 简写为 n 的 2 次方
O(n^2)

因此，代码中循环了 m 层，时间复杂度就是 O(n^m)。如果代码中没有循环，那么时间复杂度就是 O(1)。

空间复杂度

理解了时间复杂度的表达规则，空间复杂度也一致，常见的空间复杂度也包括：

O(1)、O(n)、O(n^2)

时间复杂度，通过循环的层级来确定 n；空间复杂度，则通过在循环中是否申请/修改变量来确定 n。

我们再看这个函数：

function traverse(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    console.log(arr[i]);
  }
}

虽然函数中有循环，但是循环体内并没有申请/修改变量，变量申请只有 2 次：

var len = arr.length;
var i = 0;

那么，这个函数的空间复杂度即为 O(1)。

如果将函数修改成这样：

function traverse(arr) {
  var len = arr.length;
  var new_arr = [];
  for (var i = 0; i < len; i++) {
    new_arr[i] = arr[i];
  }
}

在循环中数组 new_arr 的长度不断被加大，内存占用不断变高，因此它的空间复杂度为 O(n)。