矩阵加法的复杂性是什么?

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

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

对于具有m行和n列的二维矩阵,它是o(m*n)。

或者你可以说它是o(l),其中l是元素总数。

通常,问题是用“大小为n”的正方形矩阵来定义的,也就是nxn。根据这个定义,矩阵加法是O(n^2),因为您必须访问每个nxn元素一次。

根据同样的定义,矩阵乘法(使用平方nxn矩阵)是O(n^3),因为您需要访问每个源矩阵中的n个元素来计算产品矩阵中的每个nxn元素。

一般来说,所有的矩阵运算都有O(n^2)的下界,因为您必须至少访问每个元素一次,才能计算涉及整个矩阵的任何内容。

想想一般的案例实施:

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

如果我们取简单的平方矩阵,那就是n x n加法