matrix - 矩阵加法的复杂度是多少？

Question

我找到了 some mentions in another question of matrix addition being a quadratic operation .但我认为它是线性的。

如果我将矩阵的大小加倍，我需要计算加法的两倍，而不是四倍。

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

我将其视为二次运算的另一个问题是，这意味着添加 3 维矩阵是三次矩阵，添加 4 维矩阵是 O(n^4)等，即使所有这些问题都可以简化为两个向量相加的问题，该问题具有明显的线性解决方案。

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

Answer 1

正如您已经注意到的，这取决于您对问题大小的定义:它是元素的总数，还是矩阵的宽度/高度。哪个是正确的实际上取决于矩阵加法是其中一部分的更大问题。

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