时间复杂度复习笔记

一、什么是时间复杂度

时间复杂度描述的是：

当数据量 n 变大时，程序运行时间的增长趋势。

它不是精确的秒数，而是看增长规律。

原因：秒数受电脑、语言、环境影响，但增长趋势由算法本身决定。

---

二、常见时间复杂度（从快到慢）

表示	名称	直观感受
O(1)	常数	数据量再大，时间几乎不变
O(log n)	对数	数据翻倍，时间只多一点点
O(n)	线性	数据翻倍，时间翻倍
O(n log n)	线性对数	比线性稍慢，常见于排序
O(n²)	平方	数据翻倍，时间变 4 倍
O(n³)	立方	数据翻倍，时间变 8 倍
O(2ⁿ)	指数	数据稍增就爆炸

---

三、常见例子

O(1)：按下标取值

a = [10, 20, 30]
x = a[1]

不管数组多长，取某个下标都很快。

---

O(n)：遍历数组

total = 0
for x in a:
    total += x

数组越长，循环次数越多。

---

O(n²)：双重循环

for i in range(n):
    for j in range(n):
        print(i, j)

n 翻倍，执行次数变 4 倍。

---

O(log n)：二分查找

while low <= high:
    mid = (low + high) // 2
    ...

每次砍掉一半，增长非常慢。

---

四、如何计算复杂度

原则

1. 只看增长最快的项
2. 忽略常数系数
3. 忽略低阶项

例子

$$\frac{n(n+1)}{2}=\frac{n^2+n}{2}$$

• $n^2$ 增长最快
• 常数 $\frac{1}{2}$ 忽略
• 低阶项 $n$ 忽略

结果：

$$O(n^2)$$

---

五、经典案例：每来一句都重新拼完整消息

场景

每来一句新消息，都把当前所有消息重新拼成一个完整字符串。

第1次：A              → 拼 1 句
第2次：A + B          → 拼 2 句
第3次：A + B + C      → 拼 3 句
...
第n次：A + B + ...    → 拼 n 句

总工作量

$$1+2+3+\cdots +n$$

等差数列求和：

$$1+2+\cdots +n=\frac{n(n+1)}{2}=\frac{n^2+n}{2}$$

化简

• 保留最高阶：$n^2$
• 去掉常数：$\frac{1}{2}$
• 去掉低阶：$n$

结果：

$$O(n^2)$$

直观对比

n	1+2+...+n	n²
10	55	100
100	5050	10000
1000	500500	1000000
10000	50005000	100000000

总量约为 $n^2$ 的一半，但增长趋势与 $n^2$ 一致。

对比：如果只拼一次

先存着，最后只拼一次：

A + B + C + ... + 第n句

总工作量是 n 句，即 O(n)。

---

六、大模型相关场景

场景	时间复杂度
消息列表 append	均摊 O(1)，n 句 O(n)
每句都重新拼完整 prompt	O(n²)
最后 join 一次	O(n)
Transformer 无 KV Cache 逐步生成	约 O(n³)
Transformer 有 KV Cache 逐步生成	约 O(n²)

Transformer 注意力复杂度

$$O(n^2\cdot d+n\cdot d^2)$$

• $n^{2}d$：注意力计算
• $n{d}^2$：前馈网络

其中：

• $n$：序列长度
• $d$：隐藏维度

---

七、一句话总结

时间复杂度就是描述“数据量变大时，程序会变慢得多快”的指标。
O(1) 最爽，O(log n) 很快，O(n) 正常，O(n²) 开始难受，O(2ⁿ) 基本不能碰。
每来一句都重新拼前面所有内容，总工作量是 $1+2+\cdots +n=\frac{n(n+1)}{2}$，化简后为 $O(n^2)$。