复杂度是什么

复杂度是衡量代码运行效率的重要度量因素。

对于同一个计算任务，不同的计算方法得到结果的过程复杂度是不一样的。根据资源消耗情况，我们可以从两个维度衡量复杂度。

1. 首先，这段代码消耗的资源是什么

一般而言，代码执行过程中会消耗 计算时间 和 计算空间，那么需要衡量的就是时间复杂度和空间复杂度。

2. 其次，这段代码对于资源的消耗是多少

我们通常不会关注这段代码对于资源消耗的绝对量，因为不管是时间还是空间，它们的消耗程度都和输入的数据量高度相关。为了更客观地衡量复杂度，我们通常会关注时间或者空间消耗量与输入数据量之间的关系。

复杂度是一个关于输入数据量n的函数。假设你的代码复杂度是f(n)，那么就用个大写字母O把f(n)括起来就可以，即O(f(n))。通常，复杂度的计算方法遵循以下几个原则：

1. 复杂度与具体的常系数无关

O(n)和O(2n)表示的是同样的复杂度。即 O(2n) = O(n + n) = O(n) + O(n)

2. 多项式级的复杂度相加的时候，选择高者作为结果

O(n²) + O(n)和O(n²)表示的是同样的复杂度。即 O(n²) = O(n²) + O(n) = O(n² + n)

注意

O(1)也是表示一个特殊复杂度。含义为某个任务通过有限可数的资源即可完成。此处有限可数的是指，与输入数据量n无关。

时间复杂度

注意

时间复杂度与代码的结构有着非常紧密的关系

时间复杂度是程序执行所耗费的时间（执行次数）。

常见的时间复杂度衡量级别有：

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)。如：

let i = 1;
let j = 2;
++i;
j++;
let m = i + j;

线性阶O(n)

代码共执行n次，则f(n) = n。时间复杂度为O(n)。

for (let i = 1; i < n; i++) {
  // 语句执行 n 次
}

对数阶O(logn)

通过不断的缩小查找范围，每次都将i * 2，假设循环x次之后i > 2，也就是说2ˣ = n，那么 x = log2ⁿ，则f(n) = log2ⁿ。时间复杂度为O(logn)。

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

线性对数阶O(nlogn)

将时间复杂度为O(logn)的代码循环n遍的话，那么它的时间复杂度就是n * O(logn)，则f(n) = nlogn。时间复杂度为O(nlogn)。

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

平方阶O(n²)

代码共执行n² + n次，则f(n) = n²。时间复杂度为O(n²)。

for (let i = 0; i < n; i++) {
  // 语句执行 n 次
  for (let j = 0; j < n; j++) {
    // 语句执行 n² 次
  }
}

立方阶O(n³)

代码共执行n³ + n² + n，则f(n) = n³。时间复杂度为O(n³)。

for (let i = 1; i < n; i++) {
  // 语句执行 n 次
  for (let j = 1; j < n; j++) {
    // 语句执行 n² 次
    for (let k = 1; k < n; k++) {
      // 语句执行 n³ 次
    }
  }
}

K 次方阶O(nᵏ)

代码共执行nᵏ + ... + n³ + n² + n次，则f(n) = nᵏ。时间复杂度为O(nᵏ)。

for (let i = 1; i < n; i++) {
  // 语句执行 n 次
  for (let j = 1; j < n; j++) {
    // 语句执行 n² 次
    for (let k = 1; k < n; k++) {
      // 语句执行 n³ 次
      // ...
    }
  }
}

指数阶O(2ⁿ)

代码共执行2ⁿ⁺¹ - 1次，则f(n) = 2ⁿ。时间复杂度为O(2ⁿ)。

function fn(n) {
  if (n === 0) return 1;
  return fn(n - 1) + fn(n - 1);
}

阶乘阶O(n!)

待举例。这类算法的时间复杂度为O(n!)。

空间复杂度

注意

空间复杂度与数据结构的设计有关

空间复杂度是程序运行所耗费的空间。

空间复杂度比较常用的有：

常数阶O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O(1)

let i = 1;
let j = 2;
++i;
j++;
let m = i + j;

线性阶O(n)

这里声明了一个大小为n的数组，所以复杂度应该是O(n)

const arr = [];
for (let i = 1; i < n; i++) {
  arr[i] = i;
}

平方阶O(n²)

这里声明了一个大小为n的数组，但是里面又开辟了一个新的大小为n的数组，即f(n) = n²，所以复杂度应该是O(n²)

const arr = [];
for (let i = 1; i < n; i++) {
  arr[i] = [];
  for (let j = 1; j < n; j++) {
    arr[i][j] = i + j;
  }
}

结论

• 一个顺序结构的代码，时间复杂度是O(1)
• 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是O(logn)
• 一个简单的 for 循环，时间复杂度是O(n)
• 两个顺序执行的 for 循环，时间复杂度是O(n) + O(n) = O(2n)，其实也是O(n)
• 两个嵌套的 for 循环，时间复杂度是O(n²)

总结

复杂度通常包括时间复杂度和空间复杂度，其中时间复杂度与代码的结构设计高度相关，空间复杂度与代码中数据结构的选择高度相关。在具体计算复杂度时需要注意以下几点：

• 复杂度与具体的常系数无关，O(n)和O(2n)表示的是同样的复杂度。
• 复杂度相加的时候，选择高者作为结果，也就是说O(n²) + O(n)和O(n²)表示的是同样的复杂度。
• O(1)也是表示一个特殊复杂度，即任务与算例个数n无关。

练习

评估以下代码片段的时间复杂度是多少

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    for (let k = 0; k < n; k++) {
      // ...
    }
    for (let m = 0; m < n; m++) {
      // ...
    }
  }
}

答案解析

代码共执行n + n² + n³ + n³次，则f(n) = n³。时间复杂度为O(n³)

for (let i = 0; i < n; i++) {
  // 语句执行 n 次
  for (let j = 0; j < n; j++) {
    // 语句执行 n² 次
    for (let k = 0; k < n; k++) {
      // 语句执行 n³ 次
      // ...
    }
    for (let m = 0; m < n; m++) {
      // 语句执行 n³ 次
      // ...
    }
  }
}