什么是时间复杂度

问题

什么是时间复杂度？如何计算算法的时间复杂度？

解答

时间复杂度衡量的是算法执行语句的次数，而不是程序具体运行的时间。随着输入规模 n 的增大，时间复杂度越大，算法花费的时间越多。

常见的时间复杂度

按增长速度从低到高排列：

• 常数阶 O(1)
• 对数阶 O(log₂n)
• 线性阶 O(n)
• 线性对数阶 O(n log₂n)
• 平方阶 O(n²)
• 立方阶 O(n³)
• k次方阶 O(nᵏ)
• 指数阶 O(2ⁿ)

计算方法

1. 选取相对增长最高的项
2. 最高项系数化为 1
3. 常数用 O(1) 表示

例如：f(n) = 3n⁴ + 3n + 300，则 O(n) = n⁴

通常计算时间复杂度时考虑最坏情况。

三种典型场景

场景 1：执行次数固定

如果算法执行时间不随 n 增长，即使有上千条语句，时间复杂度也是 O(1)。

let x = 1;
while (x < 100) {
  x++;
}

执行 100 次是常数，复杂度为 O(1)。

场景 2：嵌套循环

时间复杂度由嵌套层数最多的循环语句中最内层语句决定。

for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    // ...code
  }
}

外层循环每执行一次，内层循环执行 n 次，时间复杂度为 O(n²)。

场景 3：条件相关的循环

循环次数不仅与 n 有关，还与执行条件有关。

for (var i = 0; i < n && arr[i] != 1; i++) {
  // ...code
}

如果 arr[i] 不等于 1，时间复杂度是 O(n)；如果 arr[i] 等于 1，循环提前结束，时间复杂度是 O(1)。

关键点

• 时间复杂度表示算法执行语句的次数，不是实际运行时间
• 计算时保留最高次项，系数化为 1，常数用 O(1) 表示
• 嵌套循环的复杂度由最内层循环决定
• 通常分析最坏情况下的时间复杂度