0. 背景

假设我们有两个矩阵：

矩阵 A，尺寸为 (n, d_k)
矩阵 B，尺寸为 (d_k, n)

我们要计算它们的乘积 C = A * B。
那么这个过程所需的计算量是多少？

1. 结果矩阵的尺寸

首先，结果矩阵 C 的尺寸是由第一个矩阵的行数和第二个矩阵的列数决定的。

C 的行数 = A 的行数 = n
C 的列数 = B 的列数 = n
所以，结果矩阵 C 的尺寸为 (n, n)。

2. 单个元素的计算量

接下来，我们看如何计算结果矩阵 C 中的任意一个元素 C_ij（第 i 行，第 j 列的元素）。

根据矩阵乘法的定义，C_ij 是由 A 的第 i 行和 B 的第 j 列的点积（dot product）得到的。

A 的第 i 行是一个有 d_k 个元素的行向量。
B 的第 j 列是一个有 d_k 个元素的列向量。

计算过程如下：
C_ij = A_i1 * B_1j + A_i2 * B_2j + ... + A_id_k * B_d_kj

为了计算这一个 C_ij 元素，我们需要：

d_k 次乘法 (每个 A_ik 乘以 B_kj)
d_k - 1 次加法 (将 d_k 个乘积相加)

3. 总计算量

现在我们来计算整个矩阵 C 的总计算量。

结果矩阵 C 是一个 (n, n) 的矩阵，所以它总共有 n * n = n^2 个元素。

我们将单个元素的计算量乘以总元素数量：

总乘法次数 = (每个元素的乘法次数) × (总元素个数)
= d_k * n^2
总加法次数 = (每个元素的加法次数) × (总元素个数)
= (d_k - 1) * n^2

4. 结论

将一个 (n, d_k) 矩阵与一个 (d_k, n) 矩阵相乘：

总乘法运算量为 n² * d_k 次。
总加法运算量为 n² * (d_k - 1) 次。

在计算机科学和机器学习领域，我们通常使用浮点运算次数 (FLOPs, Floating Point Operations) 来衡量计算量。一次乘法和一次加法通常被打包看作一次操作（特别是在现代硬件的FMA指令中）。

总FLOPs ≈ 总乘法次数 + 总加法次数
= (n² * d_k) + (n² * (d_k - 1))
= n² * (d_k + d_k - 1)
= n² * (2d_k - 1)

当 d_k 比较大时，我们通常近似为 2 * n² * d_k FLOPs。

5. 应用背景（非常重要）

这个计算 (n, d_k) * (d_k, n) 在 Transformer模型 的自注意力（Self-Attention）机制中非常核心。

n 通常代表序列长度（Sequence Length）。
d_k 代表Query和Key向量的维度。

这个计算对应的是 Query (Q) 矩阵 和 Key (K) 矩阵的转置 (Kᵀ) 相乘，以得到注意力分数矩阵（Attention Score Matrix）。

Q 的尺寸是 (n, d_k)
K 的尺寸是 (n, d_k)，所以 Kᵀ 的尺寸是 (d_k, n)
Q * Kᵀ 的结果是一个 (n, n) 的矩阵，其计算复杂度就是 O(n² * d_k) 。

这也解释了为什么标准Transformer模型的计算量和内存占用会随着序列长度 n 的增加而呈平方级增长，这是限制其处理非常长序列的主要瓶颈之一。

6. 附录(泛化)

补充一种更加泛化的计算方式。我们来分析一下将一个 (a, b) 矩阵与一个 (b, c) 矩阵相乘的计算量。

假设我们有两个矩阵：

矩阵 A，尺寸为 (a, b) （a 行, b 列）
矩阵 B，尺寸为 (b, c) （b 行, c 列）

我们要计算它们的乘积 C = A * B。

6.1 结果矩阵的尺寸

首先，结果矩阵 C 的尺寸由 A 的行数和 B 的列数决定。

C 的行数 = A 的行数 = a
C 的列数 = B 的列数 = c
所以，结果矩阵 C 的尺寸为 (a, c)。

6.2 单个元素的计算量

接下来，我们计算结果矩阵 C 中的任意一个元素 C_ij（第 i 行, 第 j 列）。

C_ij 是由 A 的第 i 行和 B 的第 j 列的点积（dot product）得到的。

A 的第 i 行是一个长度为 b 的行向量。
B 的第 j 列是一个长度为 b 的列向量。

计算公式为：
C_ij = A_i1 * B_1j + A_i2 * B_2j + ... + A_ib * B_bj

为了计算这一个 C_ij 元素，我们需要：

b 次乘法
b - 1 次加法

6.3 总计算量

结果矩阵 C 是一个 (a, c) 的矩阵，它总共有 a * c 个元素。

我们将单个元素的计算量乘以总元素数量，得到整个矩阵的计算量：

总乘法次数 = (每个元素的乘法次数) × (总元素个数)
= b * (a * c)
= a * b * c
总加法次数 = (每个元素的加法次数) × (总元素个数)
= (b - 1) * (a * c)
= a * c * (b - 1)

6.4 结论与总结

对于一个 (a, b) 矩阵和一个 (b, c) 矩阵的乘法：

总乘法运算量为 a * b * c 次。
总加法运算量为 a * c * (b - 1) 次。

在衡量算法复杂度时，我们通常使用 Big O 表示法，或者计算总的 浮点运算次数 (FLOPs)。

总FLOPs ≈ 总乘法次数 + 总加法次数
= (a * b * c) + (a * c * (b - 1))
= a * c * (b + b - 1)
= a * c * (2b - 1)
时间复杂度 (Time Complexity)：
当 a, b, c 都很大时，常数 2 和 -1 可以忽略。因此，计算复杂度为 O(abc)。