📐 计算复杂度分析：完整推导

变量定义：

• $n$ = 序列长度
• $d$ = 模型维度（$d_\text{model}$）
• $L$ = Transformer 层数

自注意力复杂度逐步分析：

步骤 1：计算 $Q, K, V$ 投影（三次矩阵乘法，每次 $(n \times d) \cdot (d \times d_k)$）：

$\text{复杂度} = 3 \times O(n \cdot d \cdot d_k) = O(n d^2) \quad \text{（通常 } d_k \approx d\text{）}$

步骤 2：计算注意力矩阵 $QK^T$（$(n \times d_k) \cdot (d_k \times n)$）：

$\text{复杂度} = O(n^2 d_k) = O(n^2 d)$

步骤 3：注意力加权 $AV$（$(n \times n) \cdot (n \times d_v)$）：

$\text{复杂度} = O(n^2 d_v) = O(n^2 d)$

步骤 4：FFN（两次线性层，$d_{ff} = 4d$）：

$\text{复杂度} = O(n \cdot d \cdot 4d) + O(n \cdot 4d \cdot d) = O(n d^2)$

单层总复杂度：

$\underbrace{O(n d^2)}_{\text{投影+FFN}} + \underbrace{O(n^2 d)}_{\text{注意力矩阵}}$

当 $n \ll d$ 时（短序列），$O(nd^2)$ 主导；当 $n \gg d$ 时（长序列），$O(n^2 d)$ 主导。

内存复杂度：需要存储注意力矩阵 $A \in \mathbb{R}^{n \times n}$，内存 $O(n^2)$。

与其他序列模型对比：

属性	Self-Attention	RNN	CNN（核大小 $k$）
单层复杂度	$O(n^2 d)$	$O(n d^2)$	$O(k n d^2)$
最大路径长度	$O(1)$	$O(n)$	$O(n/k)$
并行化	完全并行	顺序（无法并行）	完全并行
长距离依赖	直接（1步）	困难（$n$ 步）	有限（取决于 $k$）