给出了三个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/