时间复杂度

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

时间复杂度用大 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$

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

对数时间复杂度

对数时间复杂度通常是指二分查找, 时间复杂度表示为 $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)$ 常见于嵌套循环, 一层循环是线性时间复杂度, 另一层循环是对数时间复杂度

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

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