一句话定义
Big O 给出资源消耗随规模增长的渐进上界,帮助比较算法的扩展性。分析时还要说明最坏、平均、摊还等口径,并区分输入参数。
为什么重要
- 预测“能不能跑完”: 时 约 2000 万次操作,实际耗时还要看每次操作的代价和实现; 是 次,要跑几个小时甚至更久。
- 选择数据结构的依据:list 查找 vs set 查找 (见 k2.ds.hash-table)。
- 理解大模型成本:标准自注意力对上下文长度是 。
使用边界
O(n²) 本身不保证翻倍必耗时四倍;增长比例只是主导项确为平方且常数因素相近时的近似。实际时间还受实现、缓存、硬件和 I/O 影响。
原理 / 图解
形式化定义:若存在常数 和 ,使得对所有 都有 ,则记 :
例:,因为 大了以后 项主导一切。
| 复杂度 | 名称 | 典型例子 |
|---|---|---|
| 常数 | 数组下标访问、哈希查找 | |
| 对数 | 二分搜索、平衡树操作 | |
| 线性 | 遍历、线性搜索 | |
| 线性对数 | 归并排序、快速排序(平均) | |
| 平方 | 冒泡排序、双重循环、标准注意力 | |
| 指数 | 朴素递归斐波那契、子集枚举 |
Python 内置类型操作的复杂度表:https://wiki.python.org/moin/TimeComplexity
可运行示例
“倍增实验”:把 从 1000 翻倍到 2000,观察不同复杂度算法的耗时倍数;再打印增长表与注意力矩阵规模(Python 3.15.0 一稿运行记录):
# 文件:examples/18_big_o.py
# Big O:输入规模翻倍时,耗时怎么变?用实测验证
import time, bisect
def timed(fn, n, reps=3):
best = float("inf")
for _ in range(reps):
t0 = time.perf_counter(); fn(n); best = min(best, time.perf_counter() - t0)
return best
data = {}
def o1(n): return data.get(n) # O(1)
def ologn(n): arr = range(n); return bisect.bisect_left(arr, n // 3) # O(log n)
def on(n): return sum(range(n)) # O(n)
def onlogn(n): return sorted(range(n, 0, -1)) # O(n log n)(逆序输入)
def on2(n): return sum(1 for i in range(n) for j in range(n)) # O(n^2)
print(f"{'复杂度':<10}{'n=1000':>12}{'n=2000':>12}{'倍数':>8}")
for name, fn, n in [("O(1)", o1, 1000), ("O(log n)", ologn, 1000), ("O(n)", on, 200_000),
("O(n log n)", onlogn, 200_000), ("O(n^2)", on2, 1000)]:
t1, t2 = timed(fn, n), timed(fn, 2 * n)
print(f"{name:<10}{t1*1e6:>10.1f}µs{t2*1e6:>10.1f}µs{t2/t1:>8.1f}")
print("理论倍数:O(1)≈1, O(log n)≈1.1, O(n)≈2, O(n log n)≈2.1, O(n^2)≈4(实测受缓存和常数影响)")
# 增长速度表
import math
print(f"\n{'n':>8}{'log n':>8}{'n log n':>12}{'n^2':>16}{'2^n':>12}")
for n in [10, 100, 1000, 10**6]:
two = f"{2**n:.1e}" if n <= 1000 else "天文数字"
print(f"{n:>8}{math.log2(n):>8.1f}{n*math.log2(n):>12.0f}{n*n:>16.0e}{two:>12}")
# Transformer 自注意力:序列长度 L 的 O(L^2) 代价
for L in [1024, 8192, 131072]:
print(f"上下文 {L:>6} tokens:注意力分数矩阵有 {L*L:>17,} 个元素")
一稿留存输出:
复杂度 n=1000 n=2000 倍数
O(1) 0.2µs 0.1µs 0.4
O(log n) 0.6µs 0.5µs 0.9
O(n) 1340.9µs 2682.0µs 2.0
O(n log n) 4529.8µs 9274.3µs 2.0
O(n^2) 13563.7µs 61019.6µs 4.5
理论倍数:O(1)≈1, O(log n)≈1.1, O(n)≈2, O(n log n)≈2.1, O(n^2)≈4(实测受缓存和常数影响)
n log n n log n n^2 2^n
10 3.3 33 1e+02 1.0e+03
100 6.6 664 1e+04 1.3e+30
1000 10.0 9966 1e+06 1.1e+301
1000000 19.9 19931569 1e+12 天文数字
上下文 1024 tokens:注意力分数矩阵有 1,048,576 个元素
上下文 8192 tokens:注意力分数矩阵有 67,108,864 个元素
上下文 131072 tokens:注意力分数矩阵有 17,179,869,184 个元素
- 、 翻倍后约 2 倍, 通常可观察到接近平方增长的趋势,具体比值受测量条件影响。
- 那一行的 异常倍数可能来自测量噪声:耗时太短(亚微秒级),计时误差占主导。
- 上下文从 8K 到 128K(16 倍),注意力分数矩阵元素多了 256 倍。
常见误区
- Big O 小就一定快:常数因子很重要。小规模时 的插入排序可能比 算法快(Timsort 对短片段就用插入排序)。
- 忽略最坏情况:快速排序平均 ,最坏 (见 k2.algo.quicksort)。
- 混淆平均、最坏、摊还:
list.append是摊还 ,单次扩容时是 。 - 只看时间不看空间:归并排序需要 额外空间。
- 忘了隐藏循环:
x in list、list.index、字符串拼接s += t在循环中都可能让复杂度悄悄升阶。
与 AI 开发的关系
- 注意力的平方代价:标准自注意力计算和存储 分数矩阵,时间 。FlashAttention 不改变计算量的阶,但通过分块避免显式存储整个矩阵,降低显存占用和 IO。https://arxiv.org/abs/2205.14135
- 向量检索:暴力检索每次查询 ;HNSW 等近似索引把查询降到经验上的亚线性。
- 数据处理管道:千万级日志或语料上,一个 去重就可能让任务跑不完。
延伸阅读
- Python Wiki 时间复杂度:https://wiki.python.org/moin/TimeComplexity
- Big-O Cheat Sheet:https://www.bigocheatsheet.com/
- 维基百科:大 O 符号 https://en.wikipedia.org/wiki/Big_O_notation
理解检查
一个 O(n) 算法同时也属于 O(n²) 吗?
参考答案:属于。Big O 是上界;要表达紧确增长阶,可以使用 Θ。
核验与复现
核验日期:2026-10-14。示例状态:运行通过。本轮日志:18_big_o.py。
配套代码与核验资料