我研究了两个 n × n 矩阵相乘的大 O 复杂度，这需要时间 O(n3)。但是，将两个维度为 m × n 和 n × r 的矩形矩阵相乘时，如何获得大 O 复杂度呢？有人告诉我答案是 O(mnr)，但我不确定这是从哪里来的。谁能解释一下？
谢谢!
最佳答案
我假设您正在谈论将两个 n × n 维方阵相乘的复杂度计算为 O(n3)，并且正在询问将 m × n 矩阵相乘的复杂度和一个 n × r 矩阵。有专门的算法可以比简单的方法更快地解决这个问题，但出于这个问题的目的，我将只讨论标准的“将每个条目的每一行乘以每一列”算法。
首先，让我们看看 O(n3) 项在两个 n × n 矩阵相乘时的来源。请注意，对于结果矩阵的每个值，位置 (i, j) 的条目由左矩阵的第 i 行和右矩阵的第 j 列的内积给出。每行和每列都有 n 个元素，因此计算每个元素需要时间 Θ(n)。这样做 Θ(n2) 次(对结果矩阵的每个元素一次)需要时间 Θ(n3)。
现在在 m × n 矩阵和 n × r 矩阵的乘积的上下文中考虑这个问题。矩阵中的条目 (i, j) 由左矩阵的第 i 行(有 n 个条目)和右矩阵的第 j 列(有 n 个条目)的内积给出，因此计算它需要时间 Θ (n).您对结果矩阵的每个元素执行一次此操作。由于生成的矩阵的维度为 m × r，因此需要考虑 Θ(mr) 个元素。因此，完成的总功为 Θ(mnr)。
希望这对您有所帮助!
关于algorithm - 两个不等维矩阵相乘的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19508022/