时间复杂度
一句话解释
时间复杂度描述如何 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.
相关术语
相关资源
相关课程
- 时间复杂度 Intro
学习关于时间复杂度.
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。