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 倍	冒泡、双层循环

二、从循环识别复杂度

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 变大时慢多少倍"的标尺：先用它筛掉明显的坏算法，再用实测和缓存分析做最终决定——分析选方向、测量定细节。

---

本文为骨架文档：核心结构已就位，示例代码与实测数据将在后续批次补齐。