代码与技术常识06 / 10
大 O 的 6 个等级
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
- 学会用时1 小时
- 你的收获数据变多时，预判哪里会先卡住
- 用到的频率每周 1 次
- 难度稍难
该复习了做一下本页的 10 秒自测，答对就能把下次复习推后。去自测
01为什么学
没学之前
数据从一百条变成十万条，页面突然卡死，不知道原因。
学会之后
看代码就能估算增长速度，提前避开 O(n²) 的陷阱。
- 能预判全文检索、去重、分页的瓶颈
- 明白为什么长上下文的注意力那么贵
02图解
数据图
03基本单元6 个
- O(1)常数
- O(log n)对数，二分查找
- O(n)线性，遍历一遍
- O(n log n)排序
- O(n²)双重循环
- O(2ⁿ)枚举所有子集
04怎么用
- 看循环一层循环 O(n)，两层嵌套 O(n²)
- 每次把范围砍一半O(log n)
- 排序通常是 O(n log n)
- 数据量大时优先减少嵌套循环用哈希表或排序加双指针
05速查表
| 等级 | 例子 |
|---|---|
| O(1) | 用下标取数组元素、查哈希表 |
| O(log n) | 二分查找 |
| O(n) | 遍历数组一遍 |
| O(n log n) | 排序 |
| O(n²) | 双重循环（如两两比较去重） |
06动手试试
数据变多，代码会慢多少
07套用一次
去重：双重循环是 O(n²)；先放进哈希集合再统计是 O(n)。数据 10 万条时，前者要十几秒，后者瞬间。
08常见的坑
忽略常数
n 很小时，O(n²) 也可能比 O(n log n) 快，别过度优化。
只看代码行数
一行代码里也可能藏着循环，比如数组的 includes。
09自测与练习
先做 10 秒自测，再动手练一下。
两层嵌套循环，每层都遍历 n 个元素，复杂度是？
10 分钟小练习
找一段自己的代码，估算它的复杂度，再用演示器看 10 万条数据大概多慢。
看参考答案
嵌套循环里再调用数组的 includes 是常见的隐藏 O(n²)。
