矩阵比较算法

Question

如果你有2个矩阵N*M的矩阵.什么是获得差异的最佳方法？

例:

2 3 2 3 2 3 2 3                      2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3                      2 3 2 3 2 3 2 3
2 3 4 5 4 3 2 3      <--->           2 3 2 3 2 3 2 3
2 3 4 5 2 3 2 3                      2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3                      2 3 2 3 2 3 2 3

                      |
                      |
                     \ /
             Rect([2,2] , [3,4])
                    4 5 4
                    4 5 2-> A (2 x 3 Matrix)

我能想到的最好的就是从左上角扫描到有差异的点.然后从右下角扫描并找到存在差异的点.

但在最坏的情况下,这是O(N*M).有更好的有效算法吗？或者我可以用我如何表示它们,以便您可以应用更有效的算法？请注意,这个矩阵可能非常大.

Answer 1

不，没有更有效的算法。对于相同的矩阵，必须扫描所有元素，因此算法必然为O(n*m)。