黑豆的博客

时间复杂度和空间复杂度是评价算法的两个重要依据，下面我们来做个简单介绍。

# 时间复杂度

算法的时间复杂度描述的是随着输入规模的增大，算法对应的执行总次数的一个变化趋势，在实际开发中并不需要去逐行计算。

我们来看一行最简单的代码：

console.log('hello world')

这行代码在程序运行的时候只执行了一次：

T(n) = 1

咱们再来看个稍微复杂点的代码：

const arr = [1, 2]

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i])
}

在程序运行后 const arr = [1, 2] 这行代码只执行了一次。

下面来拆分 for 循环中的代码看看 let i= 0 这行代码执行了一次， i < arr.length 执行了 n + 1 次， i++ 这行执行了 n 次，console.log(arr[i]) 这行代码执行了 n 次。所以上面的代码总共执行了：

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

再来看一个复杂点的：

const arr = [1, 2, 3]
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    console.log(arr[j])
  }
}

用上面的方法分析这段代码执行了多少次：

// 1
const arr = [1, 2, 3]
//       1           n+1         n
for (let i = 0; i < arr.length; i++) {
  //    n          n*(n+1)        n*n
  for (let j = 0; j < arr.length; j++) {
    //      n*n
    console.log(arr[j])
  }
}

得：

T(n) = 1 + 1 + n + 1 + n + n + n * (n + 1) + n * n => 3n^2 + 4n + 3

简化规则：

  • 若 T(n) 是常数，那么无脑简化为1
  • 若 T(n) 是多项式，比如 3n^2 + 4n + 3，我们只保留次数最高那一项，并且将其常数系数无脑改为1。

通过简化，以上例子的时间复杂度分别为：

T(n) = 1 => O(n) = 1
T(n) = 3n + 3 => O(n) = n
T(n) = 3n^2 + 4n + 3 => O(n) = n^2

再来看一个例子：

const arr = [1, 2, 3]
for (let i = 1; i < arr.length; i = i * 2 ) {
  console.log(arr[i])
}

可以看到上面的代码和之前的的代码有个特殊的地方，就是 i = i * 2 ，之前的代码是 i++ 因为这个条件的变化，对于代码的时间复杂度分析就难了些。

前面的代码的 n 可以暂时理解为数组的长度，这里我们依然把 n 理解为数组的长度，跳出 for 循环的条件 i < n 可以理解成 i >= n，换而言之可以理解成 i 按照 i = i * 2 的规则递增 x 次后 i>=n 依然成立，举例如下：

i = 1 => i * 2 => 2
i = 2 => i * 2 => 4
i = 4 => i * 2 => 8
i = 8 => i * 2 => 16
i = 16 => i * 2 => 32
...

从上面可以看出来递增 x 后，i 的值为 2^x 。也就是我们需要解的式子如下：

2^x >= n => n = log2n

底数和系数都可以被省略，得

O(n) = logn

所以上面代码的时间复杂度为 logn 。

常见的时间复杂度有以下几种：

# 空间复杂度

空间复杂度用来描述在程序运行期间内存的增长趋势。

常见的空间复杂度有：O(1)、O(n) 和 O(n^2)

const arr = [1, 2, 3]
for (var i = 0, len = arr.length; i < len; i++) {
  console.log(arr[i])
}

上面的代码总共有三个变量：

arr
i
len

随着代码的运行，内存空间并不会有什么增加，所以对应的空间复杂度为 O(1) 。

let n = 10  // n 的值可变
const arr = []
for (var i = 0; i < n; i++) {
  arr[i] = i
}

上述代码中的变量有：

n
arr
i

上述代码由于数组 arr 的大小由 n 的大小决定，随着 n 的变化线性变化，所以上述代码的空间复杂度为 O(n) 。

由于现在的设备性能越来越好，内存也越来越大，一般情况下我们更多的会考虑一个算法的时间复杂度，很多时候我们会用空间换时间。

← 数组实操 →