矩阵加法的复杂度是多少？
我找到some mentions in another question of matrix addition being a quadratic operation了。但我认为它是线性的。
如果我将一个矩阵的大小加倍，我需要计算两倍的加法，而不是四倍。
主要的分歧点似乎是问题的大小。对我来说，它是矩阵中元素的数量。其他人认为它是列数或行数，因此是O(n^2)的复杂性。
我将其视为二次运算的另一个问题是，这意味着添加3维矩阵是立方的，添加4维矩阵是O(n^4)，等等，即使所有这些问题都可以简化为添加两个向量的问题，这有一个明显的线性解。
我是对还是错？如果错了，为什么？
回答 4
Stack Overflow用户
发布于 2009-12-09 06:35:25
正如您已经注意到的，这取决于您对问题大小的定义:是元素的总数，还是矩阵的宽/高。哪一个是正确的，实际上取决于矩阵加法所涉及的更大的问题。
注意:在某些硬件(GPU、向量机等)上，加法可能比预期运行得更快(尽管复杂性仍然相同，请参阅下面的讨论)，因为硬件可以在一步中执行多个加法。对于一个有界的问题大小(如n< 3)，它甚至可能是一个步骤。
Stack Overflow用户
发布于 2009-12-09 06:37:40
对于一个M行N列的二维矩阵，它是O(M*N)。
或者你可以说它是O(L)，其中L是元素的总数。
Stack Overflow用户
发布于 2009-12-09 06:43:28
通常使用“大小为N”的方阵来定义问题，即NxN。根据这个定义，矩阵加法是O(N^2)，因为您必须恰好访问每个NxN元素一次。
根据同样的定义，矩阵乘法(使用正方形NxN矩阵)是O(N^3)，因为您需要访问每个源矩阵中的N个元素来计算乘积矩阵中的每个NxN元素。
通常，所有矩阵运算的下界都是O(N^2)，因为您必须至少访问每个元素一次，才能计算涉及整个矩阵的任何内容。
https://stackoverflow.com/questions/1870336
复制相似问题
腾讯云开发者
