矩阵加法的复杂度是什么？

Question

我在另一个问题中看到有人提到矩阵加法是二次操作，但我认为它是线性的。

如果我把一个矩阵的大小加倍，我需要计算双倍的加法，而不是四倍。

主要分歧似乎在于问题的规模大小。对我来说，这是矩阵中元素的数量。其他人则认为是列数或行数，因此复杂度为O(n^2)。

我认为将矩阵加法视为二次操作是有问题的，因为这意味着添加三维矩阵是立方的，添加四维矩阵是O(n^4)等等，尽管所有这些问题都可以归结为添加两个向量的问题，而向量的解决方案显然是线性的。

我的观点是对还是错？如果错了，为什么？

- R. Martinho Fernandes

---

您是将矩阵的总元素数量加倍，还是将每个维度的矩阵加倍？ - Andres

为什么要踩我？这个问题不清楚或者没有用吗？ - R. Martinho Fernandes

Answer 1

正如你已经注意到的那样，这取决于你对问题规模的定义：是元素的总数，还是矩阵的宽度/高度。哪一个是正确的实际上取决于矩阵加法所属的更大问题。

注：在某些硬件（GPU、向量机等）上，加法可能比预期运行得更快（即使复杂度仍然相同，请参见下面的讨论），因为硬件可以一次执行多个加法。对于有界问题大小（如n < 3），它甚至可能只需要一步。

- akuhn

---

硬件不会改变渐近复杂度。它可以一次执行更多的加法，但您不能用比矩阵中的元素更少的加法添加两个矩阵。这是一个常见的误解，特别是在多线程中。事实上，它运行得更快并不意味着它的渐近复杂度较低。 - R. Martinho Fernandes

这就是我过于深思熟虑而太晚得出的结果。为什么两种观点不能都正确呢？现在我感觉很愚蠢。 - R. Martinho Fernandes

我认为逻辑有点作弊。 - rlbond

除了这个（非常好的）答案之外，还要考虑到如果计算的数据超过了内存缓存的大小，你会遇到麻烦。 - Nick Vaccaro

是的，常数在大O表示法中并不考虑；但是您可能会将时间复杂度与操作次数复杂度混淆。 - dfa

Answer 2

对于一个有M行N列的二维矩阵，时间复杂度为O(M*N)。

或者你可以说它的时间复杂度为O(L)，其中L是元素总数。

- rlbond

Answer 3

通常问题使用大小为N的方阵来定义，意思是NxN。根据这个定义，矩阵加法的时间复杂度为O(N^2)，因为你必须恰好访问每一个NxN元素一次。

同样根据这个定义，矩阵乘法（使用方阵NxN）的时间复杂度为O(N^3)，因为你需要访问源矩阵中每个元素N次，以计算产品矩阵中的每个NxN元素。

通常来说，所有矩阵操作都有一个时间复杂度的下限为O(N^2)，因为你必须至少访问每个元素一次才能计算涉及整个矩阵的任何内容。

- Drew Hall

---

所有密集矩阵的操作，稀疏矩阵的操作都受非零条目的限制。 - akuhn

@Adrian：抱歉...我没有考虑到这里的稀疏/带状/其他结构化矩阵。 - Drew Hall

Answer 4

想象一下通用情况的实现：

for 1 : n
 for 1 : m
   c[i][j] = a[i][j] + b[i][j]

如果我们考虑一个简单的方阵，即n x n的加法。

- µBio