大 O 记号
一句话解释
大 O 记号描述算法运行时间或内存随输入规模增长的趋势,忽略常数项。
用大白话说
大 O 记号是一种数学方式,描述算法最坏情况下随输入规模 n 趋向无穷时的增长率。它关注主项,忽略常数因子和低阶项,让你能一眼比较算法。常见增长率从快到慢:O(1) 常数(哈希查找)、O(log n) 对数(二分查找)、O(n) 线性(单层循环)、O(n log n) 线性对数(好的排序)、O(n²) 平方(嵌套循环)、O(2^n) 指数(朴素递归)。对于足够大的 n,O(n log n) 算法总会胜过 O(n²),与常数无关。大 O 帮你思考可扩展性。一个 O(n²) 算法对 100 项用 1ms,对 1000 项就要 100ms,对 10000 项要 10 秒——增长率而非绝对速度决定了代码如何扩展。大 Ω 是下界,大 Θ 是紧界;大 O 是上界,也最常用。
示例
javascript
// 比较增长率
function constant(n) { return 1; } // O(1)
function logarithmic(n) { return Math.log2(n); } // O(log n)
function linear(n) { return n; } // O(n)
function quadratic(n) { return n * n; } // O(n^2)
const n = 1000;
console.log("O(1): ", constant(n)); // 1
console.log("O(log n): ", logarithmic(n)); // ~10
console.log("O(n): ", linear(n)); // 1000
console.log("O(n^2): ", quadratic(n)); // 1000000n=1000 时各增长率差距巨大。大 O 刻画这种渐近差异,忽略常数。
相关术语
相关资源
相关课程
- 算法
学习大 O 与复杂度分析。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。