矩阵加法的复杂度是多少？
我发现另一个问题中提到了矩阵加法是二次运算。但我认为这是线性的。
如果我将矩阵的大小加倍，我需要计算加法的两倍，而不是四倍。
主要分歧点似乎是问题的严重程度。对我来说，它是矩阵中元素的数量。其他人认为它是列数或行数，因此复杂度为 O(n^2)。
我将其视为二次运算时遇到的另一个问题是，这意味着添加 3 维矩阵是三次，添加 4 维矩阵是 O(n^4) 等，即使所有这些问题可以简化为两个向量相加的问题，它有明显的线性解。
我是对还是错？如果错了，为什么？
I have found some mentions in another question of matrix addition being a quadratic operation. But I think it is linear.
If I double the size of a matrix, I need to calculate double the additions, not quadruple.
The main diverging point seems to be what is the size of the problem. To me, it's the number of elements in the matrix. Others think it is the number of columns or lines, hence the O(n^2) complexity.
Another problem I have with seeing it as a quadratic operation is that that means adding 3-dimensional matrices is cubic, and adding 4-dimensional matrices is O(n^4), etc, even though all of these problems can be reduced to the problem of adding two vectors, which has an obviously linear solution.
Am I right or wrong? If wrong, why?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
对于 M 行 N 列的二维矩阵，其复杂度为 O(M*N)。
或者你可以说它是 O(L)，其中 L 是元素总数。
It's O(M*N) for a 2-dimensional matrix with M rows and N columns.
Or you can say it's O(L) where L is the total number of elements.
正如您已经指出的，这取决于您对问题大小的定义：是元素总数，还是矩阵的宽度/高度。哪个是正确的实际上取决于矩阵加法所属的更大问题。
注意：在某些硬件（GPU、向量机等）上，加法的运行速度可能比预期更快（即使复杂性仍然相同，请参阅下面的讨论），因为硬件可以一步执行多个加法。对于有限的问题大小（例如 n < 3），它甚至可能是一步。
As you already noted, it depends on your definition of the problem size: is it the total number of elements, or the width/height of the matrix. Which ever is correct actually depends on the larger problem of which the matrix addition is part of.
NB: on some hardware (GPU, vector machines, etc) the addition might run faster than expected (even though complexity is still the same, see discussion below), because the hardware can perform multiple additions in one step. For a bounded problem size (like n < 3) it might even be one step.
通常，问题是使用“大小为 N”的方阵定义的，即 NxN。根据该定义，矩阵加法的复杂度为 O(N^2)，因为您必须恰好访问每个 NxN 元素一次。
根据相同的定义，矩阵乘法（使用 NxN 方阵）为 O(N^3)，因为您需要访问每个源矩阵中的 N 个元素来计算乘积矩阵中的每个 NxN 元素。
一般来说，所有矩阵运算的下限都是 O(N^2)，因为您必须至少访问每个元素一次才能计算涉及整个矩阵的任何内容。
Usually the problem is defined using square matrices "of size N", meaning NxN. By that definition, matrix addition is an O(N^2) since you must visit each of the NxN elements exactly once.
By that same definition, matrix multiplication (using square NxN matrices) is O(N^3) because you need to visit N elements in each of the source matrices to compute each of the NxN elements in the product matrix.
Generally, all matrix operations have a lower bound of O(N^2) simply because you must visit each element at least once to compute anything involving the whole matrix.
考虑一般情况的实现：
如果我们采用简单的方阵，即 nxn 加法
think of the general case implementation:
if we take the simple square matrix, that is n x n additions