算法如何随输入规模扩展：拆解 Big-O
发布: (2026年2月23日 GMT+8 10:16)
3 分钟阅读
原文: Dev.to
Source: Dev.to
Big‑O 表示法
“O” 代表 “order of”，用于描述算法的时间或空间需求随输入规模 n 增大时的上界（最坏情况）增长率。
计算时间复杂度
确定输入
找出什么是输入并用 n 表示其规模。
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
}此处，n = arr.length。
统计循环内部的操作
关注出现次数最多的操作。
简单 for 循环
for (let i = 0; i < n; i++) {
// ...
}→ O(n)
嵌套循环
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// ...
}
}→ O(n²)
输入规模减半的循环（二分查找模式）
while (low <= high) {
mid = Math.floor((low + high) / 2);
// ...
}→ O(log n)
递归调用（例如阶乘）
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}→ O(n)（阶乘函数本身的递归调用次数是线性的；原文中 “n log n” 的标注是错误的）
简化表达式
O(3n + 10)→ O(n)O(n² + n)→ O(n²)
常见时间复杂度
| 复杂度 | 描述 |
|---|---|
| O(1) | 常数时间——执行时间不随输入规模变化。 |
| O(log n) | 对数时间——典型于二分查找；每一步将问题规模减半。 |
| O(n) | 线性时间——对输入进行一次遍历。 |
| O(n log n) | 线性对数时间——常见于高效排序算法（如归并排序、堆排序）。 |
| O(n²) | 二次时间——对相同规模的输入进行嵌套循环。 |
| O(n³) | 三次时间——三个嵌套循环。 |
| O(2ⁿ) | 指数时间——每个元素产生两个递归调用（例如朴素递归实现的斐波那契）。 |
| O(n!) | 阶乘时间——输入的全排列（例如暴力求解的旅行商问题）。 |
复杂度的有序列表（从快到慢）
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)理解时间复杂度对于编写高效且可扩展的代码至关重要。通过使用 Big‑O 表示法，你可以分析算法的性能随输入规模的变化，并据此做出选择，以决定采用哪种方案。在设计和优化程序时，请牢记这些复杂度。