内容摘要
O(n) 比 O(n²) 快多少 · 同一任务不同算法的代价 灏 灏天文库 · 算法与数学基础 第 1 期 · 连载中 算法与数学基础 · 第 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 倍。