Skip to content

大 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));    // 1000000

n=1000 时各增长率差距巨大。大 O 刻画这种渐近差异,忽略常数。

相关术语

相关资源

相关课程

  • 算法

    学习大 O 与复杂度分析。

解读错误信息

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

查看错误

← 返回术语表