C 语言算法复杂度入门
更新时间：2026-08-26。本文是
languages/c/主题高手层的骨架文档（占位），完整展开将在后续批次补齐。
本文要回答的问题
- 大 O 到底在衡量什么？"n" 是什么？
- O(1)、O(log n)、O(n)、O(n²) 差距有多大？
- 复杂度分析说 O(n²) 很慢，为什么小数据上根本看不出来？
一、大 O 的含义
大 O 描述规模 n 增长时，运行时间（或空间）的增长率上界，忽略常数和低阶项。它回答的是"n 翻倍时慢几倍"，不是"跑几秒"。
| 复杂度 | n 翻倍的表现 | 例子 |
|---|---|---|
| O(1) | 不变 | 数组按下标访问、hash 查找 |
| O(log n) | +1 次操作 | 二分查找、平衡树 |
| O(n) | 翻倍 | 单次遍历 |
| O(n log n) | 略超翻倍 | 快排、归并 |
| O(n²) | 4 倍 | 冒泡、双层循环 |
"翻倍后慢几倍"用台阶图表示最直观：O(1) 永远平、O(log n) 缓、O(n) 直线、O(n²) 陡——同样从 n 到 2n，台阶高度天差地别：
四个台阶从左到右越来越陡，对应表格里"n 翻倍的表现"——这也正是为什么小 n 时 O(n²) 看着还行，n 一大就崩（下一节的实测会印证）。
二、从循环识别复杂度
c
for (i = 0; i < n; i++) /* O(n) */
for (j = 0; j < n; j++) /* O(n²) */
for (i = n; i > 0; i /= 2) /* O(log n) */递归则按递推式算（如二分递归 T(n)=T(n/2)+O(1) → O(log n)；分治 T(n)=2T(n/2)+O(n) → O(n log n)）。
三、复杂度 ≠ 实测速度
- 复杂度看增长趋势，常数项被忽略：O(n) 但常数巨大的实现可能比 O(n²) 常数极小的实现更慢（n 小时）。
- 实测还要算缓存局部性（见 链表与二叉树）与 编译优化。
- 正确姿势：先复杂度分析选方向，再
perf实测定细节，见 perf 使用指南。
实测：O(n) vs O(n²) 的真实差距
同样 n = 20000：
c
// O(n)：单层循环
for (int i = 0; i < n; i++) s1 += i;
// O(n²)：双层循环
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) s2 += (i + j) & 1;实测（-O0，n=20000）：
text
O(n) 单层循环 n=20000: 0 ms ← 2 万次，瞬间完成
O(n²) 双层循环 n=20000: 1030 ms ← 4 亿次，1 秒多同样的 n，O(n) 是 2 万次运算、O(n²) 是 4 亿次运算，差距是 n 倍——这就是大 O 的意义：它不告诉你"跑几秒"，而是警告你"n 翻倍后这个算法会慢多少倍"。
四、与入门层的衔接
一句话总结
大 O 是"n 变大时慢多少倍"的标尺：先用它筛掉明显的坏算法，再用实测和缓存分析做最终决定——分析选方向、测量定细节。
本文已完成填充：示例代码与实测数据已补齐。