算法对不对是一回事，快不快是另一回事。今天学「数步子」：一层循环 O(n)、两层 O(n²)、每次减半 O(log n)——再拿「每秒 1 亿步」的预算比一比，就知道 n = 10 万时谁来得及、谁超时（TLE）。
电脑再快，也有「体力上限」：竞赛裁判机大约 每秒 1 亿步（10⁸ 步/秒），限时 1 秒——你的算法总共只能花 1 亿步。数据规模 n 一变大，「步数」就不是 n、而是 n²、n³ 地涨：n = 10 万时，n² = 100 亿步，要跑 100 秒——裁判早按了「超时」。大 O 记号就是「步子账本」：不数精确步数，只记随 n 增长最快的那一项——2n + 50 记成 O(n)，3n² + n 记成 O(n²)，因为 n 大了以后，平方项、立方项会「吃掉」所有小的。
怎么数？看循环：一层 for 跑 n 圈 → O(n)；两层各 n 圈嵌套 → O(n²)；每圈把问题砍半（x = x / 2、二分查找）→ 只砍 log₂n 次就砍完 → O(log n)；树图遍历「每个点一次、每条边一次」→ O(n + m)。空间账本更简单：开了几个数组、多大——int 一个 4 字节，int g[1000][1000] 就是 100 万个 int ≈ 4 MB；递归调 n 层就是 O(n) 的调用栈。
为什么二分查找只要 log n 步？10000 个数里找一个：每次看正中间，不对就扔掉一半——10000 → 5000 → 2500 → 1250 → … → 1，13 次就定位；顺序查最坏要 10000 次。「每次减半」是图论之外最强大的加速技巧，没有之一。
// ── n = 10000 时的步数对照表 ── // 复杂度 n = 10000 时的步数 1 秒预算(1 亿步)够不够 // O(1) 1 步 绰绰有余 // O(log n) 13 步(2^13 = 8192 < 10000) // O(n) 10000 步 绰绰有余 // O(n log n) 10000 x 13 ≈ 130000 绰绰有余 // O(n^2) 10000^2 = 1 亿步 擦边(1 秒) // O(n^3) 10000^3 = 1000 亿步 要 100 秒 ✗ // O(2^n) 2^10000 = 天文数字 宇宙毁灭都跑不完 ✗
// ── 看循环：时间复杂度 ── // 一层 for 跑 n 圈 → O(n) // 两层嵌套、各 n 圈 → O(n x n) = O(n^2) // 每圈把问题砍半 → O(log n)（二分、快速幂） // 外层 n 圈、内层 m 圈 → O(n x m) // 外层 n、内层固定 k 圈 → O(n)！k 是常数，忽略 // 串联执行（先后各跑一遍）→ 取最大的：O(n^2) + O(n) = O(n^2) // 2n + 50 圈 → O(n)（常系数扔掉） // 树图遍历：每点一次每边一次 → O(n + m) // ── 数数组：空间复杂度 ── // 1 个 int = 4 字节 // int g[500][500] → 25 万个 int x 4 B = 100 万 B ≈ 1 MB // int a[1000000] → 100 万个 int = 4 MB // 递归套 n 层 → 调用栈 O(n)
x = 10000; while (x > 1) x = x / 2; 一共跑几圈？② 外层 i 跑 n 圈、内层 j 跑 m 圈，复杂度？③ int g[500][500]; 占多少内存？// ── 查找 ── // 顺序查找（逐个比） → O(n)，最坏查遍全部 // 二分查找（必须有序） → O(log n)，每次扔一半 // ── 排序 ── // 冒泡 / 选择 / 插入 → O(n^2)，简单但慢 // 快速 / 归并 / 堆 → O(n log n)，竞赛主力 // ── 树 / 图 ── // DFS / BFS 遍历 → O(n + m)：n 个点 + m 条边 // Dijkstra（数组版） → O(n^2) // Floyd 全源最短路 → O(n^3)，n 别超几百 // Kruskal（排序选边） → O(m log m) // ── 动态规划 ── // DP = 状态数 x 每个状态的转移数 // 爬楼梯 n 级 → O(n) // 01 背包 n 件容量 v → O(n x v) // ── 快慢排序（从小到大）── // O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)
// ── 裁判预算：每秒 10^8 步 ── // n = 10^5 = 10 万时： // O(n) = 10^5 ✓ 0.001 秒 // O(n log n) = 10^5 x 17 ≈ 1.7x10^6 ✓ 0.02 秒 // O(n^2) = 10^10 ✗ 约 100 秒 → TLE // O(n^3) = 10^15 ✗ 10 万秒 → TLE // ── 决策速查表（n 多大 → 极限复杂度）── // n ≤ 10^2 (100) → O(n^3) 可用，O(n^2) 随便用 // n ≤ 10^3 ~ 10^4 → O(n^2) 是极限，O(n^3) 危险 // n ≤ 10^5 ~ 10^6 → O(n log n) 是极限，O(n^2) 超时 // n ≥ 10^6 → 只能 O(n) / O(log n) 级别 // ── 空间账本（128 MB 限制）── // 1 个 int = 4 B // 10^5 个 int = 400 KB ✓ // 10^6 个 int = 4 MB ✓ // 10^7 个 int = 40 MB 紧但能过 // int[10^4][10^4] = 1 亿个 = 400 MB ✗ 爆
int a[10000000]; 占 40 MB，限制 16 MB，会怎样？// 数据：a[1..20] = 10, 20, 30, ..., 200（从小到大，共 20 个） // 任务：找 x = 200（在队尾），数一数两种方法各比较几次 #include <iostream> using namespace std; int main() { int a[21]; for (int i = 1; i <= 20; i++) a[i] = i * 10; // a[1]=10 ... a[20]=200 int x = 200; // ── 方法 1：顺序查找（从头一个个比）── int pos1 = -1, cmp1 = 0; for (int i = 1; i <= 20; i++) { cmp1++; // 每比一次 +1 if (a[i] == x) { pos1 = i; break; } } cout << "顺序查找：比较 " << cmp1 << " 次，位置 " << pos1 << endl; // 输出：顺序查找：比较 20 次，位置 20（200 在最末尾，比了全部 20 个） // ── 方法 2：二分查找（每次看中间，扔一半）── int low = 1, high = 20, pos2 = -1, cmp2 = 0; while (low <= high) { int mid = (low + high) / 2; cmp2++; // 每比一次 +1 if (a[mid] == x) { pos2 = mid; break; } else if (a[mid] < x) low = mid + 1; // 中间比目标小 → 目标在右半 else high = mid - 1; // 中间比目标大 → 目标在左半 } cout << "二分查找：比较 " << cmp2 << " 次，位置 " << pos2 << endl; // 输出：二分查找：比较 5 次，位置 20 // 过程：mid=10(100<200)→右；mid=15(150<200)→右；mid=18(180<200)→右； // mid=19(190<200)→右；mid=20(200==200)→命中！共 5 次 // 把 x 换成 10（在队首）再想想：顺序查找 1 次就命中；二分查找 mid=10→5→2→1 // 要 4 次——「目标靠前时线性更快」。但最坏情形（目标在最末或不存在） // 线性要 20 次、二分只要 5 次：n 越大差距越悬殊（n=10 万时 10 万 vs 17）。 return 0; } // 运行结果： // 顺序查找：比较 20 次，位置 20 // 二分查找：比较 5 次，位置 20