algorithm - 两个不等维矩阵相乘的时间复杂度是多少？

Question

我已经查看了将两个 n × n 矩阵相乘的大 O 复杂性，这需要时间 O(n ³ )。但是，将两个维度为 m × n 和 n × r 的矩形矩阵相乘，如何获得大 O 复杂度？有人告诉我答案是 O(mnr)，但我不确定这是从哪里来的。谁能解释一下？

谢谢！

Answer 1

我假设您正在谈论将两个维度为 n × n 的方阵相乘到 O(n ³ ) 的复杂性，并且正在询问将一个 m × n 矩阵和一个 n × r 矩阵相乘的复杂性。有专门的算法可以比简单的方法更快地解决这个问题，但是为了这个问题的目的，我将只讨论标准的“将每一行乘以每个条目的每一列”算法。

首先，让我们看看 O(n ³ ) 项在将两个 n × n 矩阵相乘时从何而来。请注意，对于结果矩阵的每个值，位置 (i, j) 处的条目由左矩阵的第 i 行和右矩阵的第 j 列的内积给出。每行和每列有 n 个元素，因此计算每个元素需要时间 Θ(n)。执行此 Θ(n ² ) 次（结果矩阵的每个元素一次）需要时间 Θ(n ³ )。

现在在 m × n 矩阵和 n × r 矩阵的乘积的背景下考虑这个问题。矩阵中的条目 (i, j) 由左矩阵的第 i 行（有 n 个条目）和右矩阵的第 j 列（有 n 个条目）的内积给出，因此计算它需要时间 Θ (n)。您对结果矩阵的每个元素执行一次。由于生成的矩阵的维度为 m × r，因此需要考虑 Θ(mr) 元素。因此，完成的总功为 Θ(mnr)。

希望这可以帮助！