算法与数学基础 · 第 1 期

O(n) 比 O(n²) 快多少

同一任务，不同算法 · time complexity in real numbers

n=1000 时，O(n²) 比 O(n) 慢 1000 倍；n=10 万时，慢 10 万倍。复杂度不是常数项的较量，是增长曲线的较量——数据量翻倍，O(n²) 的代价翻 4 倍，O(2ⁿ) 的代价直接爆炸。
⏱ 约 9 分钟 🎯 写过算法但没算过代价的人 📦 源：OI-wiki · 复杂度

01一个反共识：常数项不重要，曲线才重要

新手常觉得"我的 O(n) 算法常数大，可能比 O(n²) 还慢"。在 n 很小时确实如此，但 n 一旦变大，曲线立刻碾压常数。

O(n) = 1000·n vs O(n²) = 1·n²

当 n=1000：左边是 100 万次操作，右边也是 100 万次，打平。当 n=1 万：左边 1000 万，右边 1 亿——O(n²) 已经慢 10 倍。当 n=10 万：左边 1 亿，右边 100 亿，慢 100 倍。常数再大也是线性的，曲线一旦分叉就再也合不上。

比的不是谁更快，
是谁涨得慢。
灏天文库 · 算法与数学基础 P.02

02复杂度对比演示：拖动 n 看代价

拖动滑块改变 n，看四种复杂度的操作数怎么变。条形长度按对数缩放（不然 O(2ⁿ) 一根条会撑爆屏幕）。

📊 复杂度对比演示
拖动 n，看 O(n) / O(n log n) / O(n²) / O(2ⁿ) 的操作数和相对代价。
n = 10
注：操作数按对数缩放为条长；O(2ⁿ) 在 n≥24 后会超出 JS 安全整数范围，本演示限制 n≤22。1 亿次操作约等于现代 CPU 0.1 秒。

03为什么 O(2ⁿ) 是"不能用的复杂度"

指数复杂度不是"慢一点"，是"宇宙都跑不完"。n=64 时，2⁶⁴ ≈ 1.8×10¹⁹ 次操作，按每秒 10 亿次算要 580 年。这就是为什么 NP-hard 问题（如旅行商的暴力解）在 n 稍大时就无解——不是算法差，是问题本身在指数爆炸。

工程上遇到指数复杂度，标准动作是换问题：用近似算法、贪心、动态规划把指数压成多项式。比如背包问题暴力是 O(2ⁿ)，动态规划能压到 O(nW)。不追求最优解，只追求"够好且能跑完"。

指数算法不是慢，
是跑不完。
灏天文库 · 算法与数学基础 P.04

04带走这套清单

✅ 复杂度 5 条可执行规则

  1. 看增长曲线，不看常数项：n 一大，曲线立刻碾压常数。
  2. O(n) 与 O(n²) 的差距随 n 增大而拉大，不是固定倍数。
  3. O(2ⁿ) 在 n≥30 时基本不可用，遇到就换问题或换算法。
  4. 估上限先看数据量：n=10⁵ 时 O(n²)=10¹⁰，已经超时。
  5. 常数项只在 n 很小或同复杂度时才重要，别本末倒置。
估得出代价，
才选得对算法。
灏天文库 · 算法与数学基础 P.05