algorithm - 在 O(n) 时间内添加方阵？

Question

假设我们有两个大小相同的方阵n，分别命名为A和B。

A并B共享其主对角线中的每个条目都是相同值的属性（即A[0,0] = A[1,1] = A[2,2] ... = A[n,n]和B[0,0] = B[1,1] = B[2,2] ... = B[n,n]）。

有没有办法表示A并且B可以在 O(n) 时间内而不是 O(n^2) 时间内将它们相加？

Answer 1

一般来说：没有。

对于nxn矩阵，有n^2要填充的输出值；这需要O(n^2)时间。

在你的情况下：不。

即使O(n)输入/输出值是相关的，O(n^2)那也是独立的。所以没有任何表示可以减少下面的整体运行时间O(n^2)。

但...

为了减少运行时间，有必要（但不一定足够）将依赖值的数量增加到O(n^2). 显然，这是否可能取决于特定场景......

Answer 2

为了补充 Oli Cherlesworth 的回答，我想指出，在sparse matrices 的特定情况下，您通常可以获得O(n).

例如，如果您碰巧知道您的矩阵是对角的，那么您也知道生成的矩阵将是对角的，因此您只需要计算n值。类似地，可以在 中添加波段矩阵，O(n)以及更多“随机”稀疏矩阵。通常，在稀疏矩阵中，每行非零元素的数量或多或少是恒定的（例如，您可以从有限元计算或图邻接矩阵等中获得这些元素），因此，使用适当的表示，例如“压缩行存储”或“压缩列存储”，您最终将使用O(n)运算来添加两个矩阵。

还特别提到了次线性随机算法，它只建议您知道与实际解决方案“不太远”的最终值，直至随机误差。