时间复杂度

时间复杂度是评估算法执行效率变化趋势的一种表达方式。它表达的是一种增长曲线趋势，而不具体的执行时间。

时间负责度用大 O 表示法来表示，他具体的公式是

$T(n) = O(f(n))$

$f(n)$ 是数学公式中对于函数的一种表达，我们也可以用代码来平替一下简化理解

1
// 针对线性时间复杂度
2
function f1(n) { 
3
  return n
4
}
5

6
// 针对平方时间复杂度
7
function f2(n) { 
8
  return n * n
9
}

函数 f1 等价于 $O(n)$

函数 f2 等价于 $O(n^2)$

线性时间复杂度

线性时间复杂度表示为 $O(n)$，对应的数学公式就是

$y = x$

在坐标系中我们可以用一条直线来表示，这条直线表示的是输入和输出的关系。x 轴表示输入，y 轴表示输出。

例如，一个普通的循环函数，时间复杂度为 $O(n)$

1
function fn(n) {
2
  for (let i = 0; i < n; i++) {
3
    console.log(i)
4
  }
5
}

该函数的执行时间，会随着输入规模 n 的增大而线性增大，时间复杂度为 $O(n)$

平方时间复杂度

平方时间复杂度通常是指嵌套循环，时间复杂度表示为 $O(n^2)$，如下案例所示

1
function fn(n) {
2
  for (let i = 0; i < n; i++) {
3
    for (let j = 0; j < n; j++) {
4
      console.log(i, j)
5
    }
6
  }
7
}

对应的数学公式是

$y = x^2$

时间复杂度用坐标系表示为

指数时间复杂度

指数时间复杂度通常是指递归，时间复杂度表示为 $O(2^n)$，如下案例所示

1
function fn(n) {  
2
  if (n <= 1) return 1
3
  return fn(n - 1) + fn(n - 2)
4
}

对应的数学公式是

$y = 2^x$

时间复杂度用坐标系表示为

由于三方工具的bug，导致曲线无法正常显示，不过移入鼠标之后可以显示坐标点，通过移动鼠标可以查看坐标点的变化趋势

对数时间复杂度

对数时间复杂度通常是指二分查找，时间复杂度表示为 $O(log_2 n)$，或者简化为 $O(log n)$，如下案例所示

1
function fn(n) {    
2
  let i = 1
3
  while (i < n) {
4
    i = i * 2
5
  }
6
}

对应的数学公式是

$y = log_2 x$

时间复杂度用坐标系表示为

线性对数时间复杂度

线性对数时间复杂度通常是指嵌套循环，一层循环是线性时间复杂度，另一层循环是对数时间复杂度，时间复杂度表示为 $O(n * log_2 n)$，或者简化为 $O(n log n)$，如下案例所示

1
function fn(n) {
2
  for (let i = 0; i < n; i++) {
3
    let j = 1
4
    while (j < n) {
5
      j = j * 2
6
    }
7
  }
8
}

对应的数学公式是

$y = n * log_2 x$

时间复杂度用坐标系表示为

总结

• 常量时间复杂度：$O(1)$ 常见于常量，变量，对象等，比较简单不单独介绍
• 线性时间复杂度：$O(n)$ 常见于普通的循环
• 平方时间复杂度：$O(n^2)$ 常见于嵌套循环
• 指数时间复杂度：$O(2^n)$ 常见于递归
• 对数时间复杂度：$O(log_2 n)$ 常见于分治算法，例如二分查找，快速排序等
• 线性对数时间复杂度：$O(n * log_2 n)$ 或者简化为 $O(n log n)$ 常见于嵌套循环，一层循环是线性时间复杂度，另一层循环是对数时间复杂度

一定要注意，时间复杂度是评估算法执行效率变化趋势的一种表达方式，而不是具体的执行时间。因此在实践设计算法中，我们可能会遇到时间复杂度相同，但是执行时间却不同的情况。

在考虑最优算法时，通常也会考虑输入规模，在输入规模足够大的时候，时间复杂度越低的算法，执行效率越高。大家可以根据具体的经验和场景来选择最优的算法。