大 O 复杂度

定义

大 O 复杂度是一种渐进表示法，用来描述算法的运行时间或占用空间随输入规模 n 增长的趋势。它刻画的是增长量级的上界，忽略常数因子和低阶项。

原理

大 O 关注 n 趋于无穷时的主导项。例如 3n²+5n+100 记为 O(n²)，因为高阶项最终主导增长。它衡量的是最坏情况上界，相对地还有表示下界的 Ω 和紧确界的 Θ。常见量级由快到慢依次为：O(1) 常数、O(log n) 对数、O(n) 线性、O(n log n)、O(n²) 平方、O(2ⁿ) 指数、O(n!) 阶乘。它帮助在不依赖具体硬件的情况下比较算法优劣。

复杂度

• 常见量级：O(1) 优于 O(log n) 优于 O(n) 优于 O(n log n) 优于 O(n²)
• 同时可衡量时间与空间

应用场景

• 算法效率分析与对比
• 面试与教学中的性能评估
• 系统设计中的可扩展性预估