并行计算场景下，传统时间复杂度模型完全失效
本文将论证：相比传统时间复杂度分析，计算工作量-计算深度（Work-Depth）模型才是更适合分析算法性能的理论工具。
讨论算法快慢时，大家第一反应永远是时间复杂度。
上世纪 80 年代，计算机普遍只有单核，极少数人才听说过 SIMD 向量指令，那时候只用时间复杂度衡量算法效率基本没问题。
但现在是 2025 年，几乎找不到单核设备，就连智能手机都配备 4–8 核处理器。正因如此，传统时间复杂度已经很难客观衡量算法实际运行速度。
仅靠时间复杂度，我们完全无法区分两种算法：一种拥有$O(n^3)$运算量、却可以极致并行；另一种运算量相同，但运算流程存在强串行依赖、无法并行。
更离谱的是，如今很多天然支持并行的线性代数算子，仍有人在用时间复杂度描述性能。
这种分析方式存在根本性缺陷。我们需要一套全新的算法复杂度分析框架，工作量-深度模型就能提供一套合适的抽象视角：不再单纯以输入规模衡量总运算量，而是从理论下界重新定义算法复杂度。
这套框架不再只关注算法总运算量（即工作量 Work），而是重点分析计算图的深度（Depth），也就是无法并行、必须串行执行的最少操作步数。无论你的设备拥有多少计算核心，这部分串行瓶颈都无法消除。
我的研究方向主要是机器学习系统性能优化，因此本文所有案例都会围绕张量运算展开。
这套模型并非完美，后文我会详细说明它的局限性；我们先从一个基础问题切入：
逐元素乘法的时间复杂度是多少？
顺着这个问题推导，最终我会提出核心论点：标准 Transformer 原生实现的注意力机制，其并行计算深度复杂度为对数级。
案例 1：逐元素乘法
给定两个长度相同的向量$\mathbf{a}$，$\mathbf{b}$，逐元素乘法会将二者同索引元素相乘，结果存入新向量$\mathbf{c}$（也可原地计算）。
伪代码如下：
1n = 超大整数
2a,b = 生成长度n的向量
3c = 全零向量，长度n
4for i in range(n):
5 c[i] = a[i] * b[i]
从传统时间复杂度视角看，该算法是线性复杂度$O(n)$；单线程运行时，这个结论确实成立。
但仔细观察计算图就能发现：循环内每一步计算完全互相独立，不存在依赖关系。
既然无依赖，自然可以全部并行执行 —— 所有线性代数、张量计算库底层也正是这么实现的。
此时你会发现，这个算法根本不存在线性串行耗时，在硬件并行算力充足的前提下，运行耗时近似常数，仅存在一个硬件阈值上限（后文详述）。
我们用工作量 - 深度模型拆解逐元素乘法：
| 操作 | 深度 | 输入数据 | 总工作量 |
|---|---|---|---|
| 读取 | 1 | $a_1,a_2\cdots a_n$ | $n$ |
| 读取 | 1 | $b_1,b_2\cdots b_n$ | $n$ |
| 乘法 | 1 | 对应元素两两相乘 | $n$ |
| 写入 | 1 | $c_1,c_2\cdots c_n$ | $n$ |
| 合计 | 4 | —— | $4n$ |
| 渐近阶 | $O(1)$ | —— | $O(n)$ |
读取、乘法、写入所有操作的计算深度均为常数。只要并行算力足够（不超过硬件阈值），整套运算的耗时可以视作常数。
案例 2：向量求和（归约运算）
向量求和（下文统称归约，Contract）比逐元素运算更复杂，运算间存在依赖：累加操作需要持续读写同一个存储变量，无法一次性全部并行。
伪代码：
1n = 超大整数
2a = 长度n的向量
3c = 0
4for i in range(n):
5 c += a[i]
但依赖仅存在于两两相加的结果之间，我们依然可以分层并行：不一次性累加全部元素，而是逐层两两合并求和。
长度为$n$的向量求和并行流程：
将相邻奇偶元素两两相加，共得到$n/2$个中间结果；
再把上一步得到的中间结果两两合并，得到$n/4$个新值；
持续逐层两两合并；
经过$log_2n$轮迭代后，最终得到唯一总和。
工作量-深度拆解表：
| 操作 | 深度 | 输入数据 | 总工作量 |
|---|---|---|---|
| 读取原始数据 | 1 | $a_1,a_2,a_3,a_4\cdots a_n$ | $n$ |
| 第一层两两加 | 1 | $a_1+a_2 , a_3+a_4\cdots$ | $\frac{n}{2}$ |
| 第二层两两加 | 1 | $[(a_1 + a_2) + (a_3 + a_4)], \cdots$ | $\frac{n}{4}$ |
| …… | …… | …… | …… |
| 最后一轮求和 | 1 | 全局总和$\Sigma a$ | 1 |
| 写入结果 | 1 | 最终总和 | 1 |
| 合计 | $\log(n) + 1$ | —— | $n+1$ |
| 渐近阶 | $O(logn)$ | —— | $O(n)$ |
案例 3：张量积
张量积是张量的基础运算，会遍历两个张量所有索引，对指定维度做逐元素相乘（部分维度可共享）。
若两个矩阵共享一个维度做张量积，会生成三阶张量；但整套运算只有并行读取、逐元素乘、写入操作，因此计算深度为常数。
限制条件：只有生成的张量（或分块张量）能完整存入缓存时，常数深度结论才成立。一旦张量超出缓存容量，内存读写会引入串行瓶颈，深度复杂度不再是常数。
机器学习领域很少单独讨论张量积，但它是统一各类张量运算的优雅框架：置换维度、求和归约、矩阵乘法、哈达玛积、广播批量运算等，本质都可以拆解为张量积 + 维度归约。
张量积工作量-深度拆解：
| 操作 | 深度 | 输入数据 | 总工作量 |
|---|---|---|---|
| 读取 A | 1 | $a_{11},a_{12}\cdots a_{13}$ | $n^2$ |
| 读取 B | 1 | $b_{11},b_{12}\cdots b_{jk}$ | $n^2$ |
| 张量积 | 1 | 全部索引逐元素相乘 | $n^3$ |
| 写入 | 1 | 生成三阶张量所有元素 | $n^3$ |
| 合计 | 4 | —— | $2n^2+2n^3$ |
| 渐近阶 | $O(1)$ | —— | $O(n^3)$ |
案例 4：矩阵乘法
矩阵乘法可以完美用张量积+维度归约描述。
设矩阵$\mathbf{A}$形状$(i,j)$、矩阵$\mathbf{B}$形状$(j,k)$：
- 张量积生成三阶张量$\mathbf{C}[i,j,k]=\mathbf{A}[i,j]\times \mathbf{B}[j,k]$；
- 沿$j$维度做归约求和，得到输出矩阵$\mathbf{D}[i,k]$。
工程上一般不会完整存储三阶张量$\mathbf{C}$，而是分块融合张量积与归约计算，节省显存。批量、广播矩阵乘法只需在外层增加批量维度即可，统一用爱因斯坦求和描述：
1einsum("...ij, ...jk -> ...ik", A, B)
底层伪代码逻辑：
1A = 形状(i,j)矩阵
2B = 形状(j,k)矩阵
3C = 全零三阶张量(i,j,k)
4
5# 张量积阶段
6for _i in range i:
7 for _j in range j:
8 for _k in range k:
9 C[_i,_j,_k] = A[_i,_j] * B[_j,_k]
10
11# 归约求和阶段
12D = 全零矩阵(i,k)
13for _i in range i:
14 for _j in range j:
15 for _k in range k:
16 D[_i,_k] += C[_i,_j,_k]
矩阵乘法是常数深度的张量积串联对数深度的归约运算，整体深度由归约操作主导：
| 操作 | 深度 | 运算说明 | 总工作量 |
|---|---|---|---|
| 读取 A | 1 | 加载矩阵 $ \mathbf{A} $ | $n^2$ |
| 读取 B | 1 | 加载矩阵 $ \mathbf{B} $ | $n^2$ |
| 张量积 | 1 | ij,jk -> ijk | $n^3$ |
| 维度归约 | $\log n$ | ijk->ik | 求和 |
| 写入输出矩阵 | 1 | 存储结果 | $\mathbf{D}$ |
| 合计 | $\log n + 4$ | —— | $2n^2 + 2n^3$ |
| 渐近阶 | $O(\log n)$ | —— | $O(n^3)$ |
案例 5：Softmax
Softmax 流程非常简单：逐元素计算指数 $\to$ 向量求和归约 $\to$ 逐元素除法。
工作量-深度分析表：
| 操作 | 深度 | 输入 | 总工作量 |
|---|---|---|---|
| 读取 | 1 | 向量$x\in \mathbb{R}^n$ | $n$ |
| 求最大值 | $\log n$ | $m=max(x)$ | $n$ |
| 减法平移 | 1 | $x^{'}=x−m$ | $n$ |
| 指数运算 | 1 | $e=\exp(x^{'})$ | $n$ |
| 求和归约 | $log n$ | $s=\Sigma(e)$ | $n$ |
| 逐元素除 | 1 | $y=\frac{e}{s} | $n$ |
| 写入 | 1 | 输出向量 $y$ | |
| 合计 | $2\log n + 5$ | —— | $7n$ |
| 渐近阶 | $O(\log n)$ | —— | $O(n)$ |
案例 6：注意力机制
铺垫完所有基础算子，我们直接分析注意力的计算深度。整套运算由多轮矩阵乘法、归约、逐元素运算串行组合而成：
| 操作 | 深度 | 输入数据 | 总工作量 |
|---|---|---|---|
| 读取输入张量 $X$ | 1 | $X\in \mathbb{R}^{b\times n\times d}$ | $bnd$ |
| 读取权重$W_q,W_k,W_v$ | 1 | $W_q,W_k,W_v \in \mathbb{R}^{d\times d}$ | $3d^2$ |
| 生成$Q/K/V$矩阵乘 | $3\log d$ | $Q=XW_q,K=XW_k,V=XW_v$ | $3bnd^2$ |
| QK转置矩阵乘 | $\log d$ | $S=QK^{\top}$ | $bn^2d$ |
| 缩放除法 | 1 | $S^{'}=\frac{S}{\sqrt{d}}$ | $bn^2$ |
| Softmax | $\log n$ | $A=softmax(S^{'})$ | $bn^2$ |
| 注意力分数乘$V$ | $\log n$ | $O=AV$ | $bn^2d$ |
| 写入输出张量$O$ | 1 | $O \in \mathbb{R}^{b\times n \times d}$ | $bnd$ |
| 总深度 | $4\log d + 2\log n + 5$ | —— | 近似$bn2d$ |
| 渐近深度阶 | $O(\log n + \log d)$ | —— | $O(bn^2d)$ |
可以看到：经过多轮矩阵乘法、归约、逐元素算子串联，标准注意力的并行计算深度复杂度仅为 $O(\log n + \log d)$，其中$n$为序列长度，$d$为嵌入维度。
实际场景中序列长度$n$通常远大于嵌入维度$d$，因此整体可简化视为$O(\log 序列长度)$。
工作量 - 深度模型的局限性
这个工作量-深度性能复杂度模型并非万能，一旦引入内存访问、缓存效率，这套理论的理想边界就会被打破。
当出现以下情况时，模型不再适用：
并行计算树的最大宽度远超硬件可用计算单元（核心 / 流多处理器）；
内存读写不连续、无法向量化；
中间生成张量无法适配硬件内存层级。
工程中，只有所有中间张量能完整存入二级缓存左右，深度复杂度理论下界才能成立；稠密张量运算通常天然具备连续内存访问，适配性更好。
为什么大家不认为注意力是对数复杂度？
现实瓶颈在于，注意力计算必须生成完整$\mathbf{Q}\mathbf{K}^{\top}$矩阵，该矩阵尺寸极大，几乎一定会超出二级缓存容量。
两种解决方案：
直接在内存中计算，速度会慢数个量级；
将$\mathbf{Q}\mathbf{K}^{\top}$矩阵分块，分段做 Softmax 归约（这就是 FlashAttention 的核心思路）。
分块操作会引入额外串行步骤，因此在普通硬件上，注意力实际有效深度复杂度接近$O(n\log n)$。但这不是算法本身固有的串行瓶颈，文末我会提出一些解决该问题的设想。
面向未来硬件的猜想
这套理论对当前芯片与下一代算力架构有极强指导意义，前提是训练范式保持前向传播$\to$反向传播循环、无大规模并行多任务并发（或是双流水线DeepSeek dualpipe等混合训练模式）。
因为模型权重占据训练过程绝大部分数据读写开销，且权重长期固定，所以硬件可以不断提升权重与计算单元的数据局部性。
行业已经出现了明显趋势：
早期权重存储在硬盘，训练时才加载至内存、再拷贝到 GPU 显存；
如今主流方案全部将权重常驻显卡高速显存（HBM）；
芯片厂商进一步将权重放置在片上二级缓存等极速存储中，直接消除缓存溢出带来的串行瓶颈（代表产品：Groq）。
原文链接
https://supaiku.com/attention-is-logarithmic
站主点评
该并行计算复杂度分析框架拆分两个核心指标评估算法并行性能：
- Work（工作量）：算法全部运算操作总量，对应传统时间复杂度，代表整体计算开销；
- Depth（计算深度）：计算图中必须串行执行的最长依赖链路步数，代表并行场景下的理论耗时下界，决定算法天然串行瓶颈；
核心逻辑是，总运算量仅衡量计算总量，计算深度才反映多核心充足并行硬件下算法的实际最低运行步数，适合 GPU 等并行设备分析张量、Transformer 算子性能。
站主认为，这一分析框架简洁而优雅，兼具启发性与创新性。当前的AI计算本质上就是超大规模的并行数值计算，引入该框架进行性能分析与指导高性能模型训练、推理系统设计，甚至是硬件和芯片设计都具有重要的应用价值。