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)。显然，这是否可能取决于特定情况...