给出了三个N * N矩阵A,B,C。 C与A和B的乘积相同,只不过一个元素是错误的。找出它的幼稚算法需要N ^ 3的时间。我们可以做得比这快吗?
最佳答案
取一个矢量v = (1 1 1 1 ... 1)
,并计算:u = Cv - A(Bv)
。u
等于(C-AB)v
,因此在除1之外的所有元素中都为零。该元素的索引对应于C不同于AB的行索引。元素(a
)的值是C-AB
中非零元素的值。
要查找列索引,可以使用向量v = (1 2 3 4 ... n)
重复此操作。现在,非零元素的值为ac
,其中a
是我们之前计算的值,而c
是列索引。
由于我们只做一些矩阵*矢量乘法,所以运行时间为O(n ^ 2)。
关于algorithm - 在矩阵乘积中找到单个错误的元素?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25505325/