⏱️
复杂度估算
时间就是钱——先算一算，程序要跑多久
💡 打个比方
O(1) 是伸手抓一颗糖 ：糖再多，也就一下。
O(log n) 是玩"二十个问题" ：每次提问把范围砍一半，100 万人里找一个，问 20 次就锁定。
O(n) 是点名 ：一个一个念，50 人的班念 50 遍，1000 人就得念 1000 遍。
O(n²) 是人人握手 ：n 个人互相握手，n 翻倍，握手量变 4 倍——人一大就崩。
大 O 记号 ：只描述"数据量 n 变大时，操作次数增长得多快"。忽略常数和低次项：3n + 5 是 O(n)，n² + 100n 是 O(n²)。n = 10⁶ 时：O(n) 约 10⁶ 次，O(n log n) 约 2×10⁷ 次，O(n²) 是 10¹² 次——差 100 万倍！
🖼️ 大图看明白
① 增长曲线：横轴是数据量 n，曲线越陡，算法越慢
操作次数 ↑
10
100
1000
10⁶
O(n²)
O(n log n)
O(n)
O(log n)
O(1)
n = 10⁶ 时：O(1)=1 次，O(log n)≈20 次，O(n)=10⁶ 次，O(n log n)≈2×10⁷ 次，O(n²)=10¹² 次（一万亿！）
② 代码形状决定复杂度
单层循环 → O(n)
for (int i = 0; i < n; i++)
doOneThing();
跑 n 次
嵌套循环 → O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
n × n 次（乘法原理）
每次减半 → O(log n)
int x = n;
while (x > 1) x = x / 2;
约 log₂(n) 次
口诀：循环相乘、忽略常数和低次项，只看最高次
📏 估复杂度，只要 3 步
第 1 步：数循环。 一层循环 ≈ n 次；两层嵌套 ≈ n × n 次；"n 每次减半"≈ log n 次。第 2 步：相乘、相加。 循环套循环 → 次数相乘 ；一段代码接一段代码 → 次数相加 （取最大的那部分）。第 3 步：扔掉常数和低次项。 3n + 5 → O(n)；n² + 100n → O(n²)。只留增长最快的那一项。
常用标尺（n = 10⁶） ：O(1) = 1 次；O(log n) ≈ 20 次；O(n) = 10⁶ 次；O(n log n) ≈ 2×10⁷ 次；O(n²) = 10¹² 次。比赛一般 1 秒能跑 10⁸ 次左右，所以 n = 10⁶ 的题目只能用 O(n) 或 O(n log n) 的算法！
💻 C++ 怎么写
// 四种代码形状，四种复杂度
void oOne(int n) { int x = 42; } // O(1)：固定几步
void oN(int n) {
int s = 0;
for (int i = 0; i < n; i++) s += i; // O(n)：跑 n 次
}
void oN2(int n) {
int s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) s++; // O(n²)：n×n 次
}
void oLog(int n) {
int x = n;
while (x > 1) x = x / 2; // O(log n)：每次减半
}考点提醒 ：① 循环边界是 n、n/2、n/4… 加起来 ≈ 2n，仍是 O(n)；② i 每次翻倍（i*=2）的循环是 O(log n)；③ 求和 1+2+…+n ≈ n²/2，是 O(n²)。
✋ 你来试试
题 1：for (i = 0; i < n; i++) 里再套 for (j = 0; j < i; j++)，复杂度是多少？
内层循环跑 i 次，总次数 = 0 + 1 + 2 + … + (n-1) = n(n-1)/2 ≈ n²/2 。扔掉常数 1/2，复杂度是 O(n²) 。判断技巧：两层循环、内外层都跟 n 有关 → 相乘 → n²。
题 2：n = 10⁶，O(n²) 算法要 10¹² 次操作。电脑每秒约 10⁸ 次，要跑多久？还能用吗？
10¹² ÷ 10⁸ = 10⁴ 秒 ≈ 10000 秒 ≈ 2.8 小时。比赛 1 秒时限，完全不够 ！所以 n = 10⁶ 的题目得选 O(n) 或 O(n log n) 的算法（比如二分查找、归并排序），不能硬套 O(n²)。
🎯 一句话记住：复杂度只看增长快慢——单层循环 n、嵌套相乘、减半 log n；忽略常数和低次项；O(1) < O(log n) < O(n) < O(n log n) < O(n²)。