计算复杂度

分类: 基础理论

计算复杂度

定义

衡量算法执行所需的资源（时间或空间）随输入规模增长的渐近行为，通常用大 O 记号表示

数学形式

核心要点

时间复杂度描述运算次数的上界，空间复杂度描述内存占用的上界

在深度学习中，常用 FLOPs 衡量模型的计算复杂度

矩阵乘法 $\mathbf{A} \in \mathbb{R}^{m \times n} \cdot \mathbf{B} \in \mathbb{R}^{n \times p}$ 的复杂度为 $O(mnp)$

代表工作

FlashHead: 将分类头复杂度从 $O(vd)$ 降至 $O(cd + pbd)$

FlashAttention: 将注意力的 IO 复杂度从 $O(N^2)$ 优化

相关概念

FLOPs

信息检索