时间复杂度 (Intro)
理解大 O notation and 时间复杂度 — 如何 描述 and compare efficiency 的 algorithms.
你将学到
- 什么时间复杂度是 and 为什么它 matters
- 大 O notation in plain language
- 常见复杂度类: O(1), O(n), O(n²), O(log n)
- 如何 estimate 复杂度的 你的 code
- 为什么 algorithm choice matters 更多 than hardware 速度
概念讲解
Time Complexity (Intro)
Time complexity is a way to describe how an algorithm's running time grows as the input size grows. It answers the question: "if I double the input, how much longer does it take?" This matters because an algorithm that is fast for 100 items might be unusably slow for a million — and you want to know that *before* you choose it.
Big O Notation
Big O notation is the language used to express time complexity. It describes the *worst-case* growth rate, ignoring constant factors and lower-order terms. The notation is O(f(n)) where n is the input size and f(n) describes how the work grows.
O(1)— constant time. The work does not depend on input size. Accessing an array element by index is O(1).O(log n)— logarithmic time. Each step halves the problem. Binary search is O(log n).O(n)— linear time. The work is proportional to input size. Scanning a list once is O(n).O(n log n)— linearithmic time. Efficient sorting algorithms (merge sort, quick sort) are O(n log n).O(n²)— quadratic time. The work is proportional to the square of the input. Nested loops over the same data are O(n²).O(2ⁿ)— exponential time. The work doubles with each added item. Naive recursive Fibonacci is O(2ⁿ).
Why It Matters
Consider two algorithms for searching a sorted list of 1,000,000 items:
- Linear search — O(n): check each item. Worst case: 1,000,000 steps.
- Binary search — O(log n): halve the range each time. Worst case: ~20 steps.
That is a 50,000× difference. No amount of hardware speed makes up for a 50,000× algorithmic disadvantage. A faster computer makes both faster, but the *ratio* stays the same. Algorithm choice dominates hardware speed for large inputs.
Estimating Complexity
You can often estimate complexity by looking at the code structure:
// O(1) — constant: one operation regardless of input
function getFirst(arr) { return arr[0]; }
// O(n) — linear: one loop over the input
function sum(arr) {
let total = 0;
for (const x of arr) total += x;
return total;
}
// O(n²) — quadratic: nested loop over the same input
function allPairs(arr) {
for (const a of arr)
for (const b of arr)
console.log(a, b);
}
// O(log n) — logarithmic: halving each step
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
The Practical Takeaway
You do not need to calculate exact Big O for every function. But you should develop an intuition: "这个有 nested 循环, 所以它是 roughly O(n²) — 如果 n 能是 10,000, 那个是 100 million 操作, 哪个可能是也慢." That intuition, more than formal proofs, is what makes you a better programmer. When you see a nested loop, ask: "是内部循环 over 相同数据? 如果所以, 这个是 O(n²) — 能 I avoid 它?"
Constants vs. Growth Rate
Big O ignores constant factors: O(2n) is written as O(n). This is because as n grows, the constant becomes irrelevant. For n = 1,000,000, the difference between n and 2n is a factor of 2 — but the difference between n and n² is a factor of 1,000,000. Big O captures the *growth*, which is what dominates at scale.
示例代码
// Compare three algorithms with different time complexity.
// Task: Check if an array contains a duplicate value.
// --- O(n²): compare every pair ---
function hasDuplicateSlow(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false;
}
// --- O(n log n): sort first, then check neighbors ---
function hasDuplicateMedium(arr) {
const sorted = [...arr].sort((a, b) => a - b);
for (let i = 1; i < sorted.length; i++) {
if (sorted[i] === sorted[i - 1]) return true;
}
return false;
}
// --- O(n): use a Set for O(1) lookups ---
function hasDuplicateFast(arr) {
const seen = new Set();
for (const item of arr) {
if (seen.has(item)) return true;
seen.add(item);
}
return false;
}
// For n = 10, all three are instant.
// For n = 100,000, the O(n²) version takes seconds,
// while the O(n) version takes milliseconds.
const data = Array.from({ length: 10000 }, (_, i) => i);
console.log(hasDuplicateFast(data)); // false (fast)
console.log(hasDuplicateMedium(data)); // false (medium)
// console.log(hasDuplicateSlow(data)); // false (slow — try at your own risk)
Three algorithms 解决相同 problem 使用不同 complexities. 设置-based 方法是 O(n) 因为设置.有() 是 O(1). nested-循环方法是 O(n²). For 大数组, difference 是 dramatic — O(n) version 是 thousands 的次数 faster.
动手试一试
- 文本 Sorter
排序是 O(n log n) 使用好 algorithms. Try 排序大 文本 and notice 它 stays 快 — 那个是 efficient 复杂度 at 工作.
- 行 Deduplicator
Deduplication 能是 O(n) 使用设置 or O(n²) 使用 nested 循环. 这个 tool uses efficient 方法.
常见错误
错误写法
Using nested 循环 over 相同数组不使用 realizing 它是 O(n²).
正确做法
当你 see 循环内部循环 over 相同数据, 停止 and ask: 能 I use 映射 or 设置到 avoid 内部循环? 经常 O(n²) algorithm 能是 rewritten as O(n) 使用 hash-based lookup.
错误写法
Optimizing code prematurely 之前 measuring 哪里 bottleneck actually 是.
正确做法
Profile 首先, optimize 其次. 快 algorithm in 很少-called 函数保存无. Focus 你的 optimization effort on code 那个运行大多数经常 or 处理大多数数据.
错误写法
Thinking 大 O 描述实际运行时间.
正确做法
大 O 描述 growth 速率, 不 milliseconds. O(n) algorithm 使用慢 常量 factor 能是 slower than O(n²) algorithm for 小输入. 大 O matters 大多数 for 大输入 and for comparing algorithms 使用不同 growth 速率.
相关资源
相关速查表
- JavaScript Cheatsheet
引用 for 设置, 映射, and 数组方法那个 affect algorithmic 复杂度.
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。