Skip to content

时间复杂度

一句话解释

时间复杂度描述如何 algorithm's 运行时 grows as 输入大小 increases, expressed in 大 O notation.

用大白话说

Time complexity is a way to describe how fast an algorithm slows down as you give it more data. If an algorithm takes 1 second for 100 items, how long does it take for 1000 items? 10000? Time complexity answers this.

Big O notation is the standard way to express time complexity:

  • O(1) — constant: same time regardless of input size (array access)
  • O(n) — linear: time grows proportionally with input (linear search)
  • O(n²) — quadratic: time grows with the square of input (bubble sort)
  • O(log n) — logarithmic: time grows very slowly (binary search)

Understanding time complexity helps you choose the right algorithm. For large datasets, the difference between O(n) and O(n²) is enormous: for 1 million items, O(n) does 1 million operations, but O(n²) does 1 trillion.

示例

javascript
// O(n) — linear search: checks each element once
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(log n) — binary search: halves the search space each step
function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Linear 搜索是 O(n) — worst 情况检查所有 n 元素. Binary 搜索是 O(log n) — halves 搜索空间每个 iteration, 所以 for 1 million 项它 takes 关于 20 steps.

相关术语

相关资源

相关课程

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表