给出了三个N * N矩阵A，B，C。 C与A和B的乘积相同，只是恰好有一个元素是错误的。找到它的天真算法需要N ^ 3时间。我们能做得更快吗？
给出了三个N * N矩阵A，B，C。 C与A和B的乘积相同，只是恰好有一个元素是错误的。找到它的天真算法需要N ^ 3时间。我们能做得更快吗？
拿一个矢量 v = (1 1 1 1 ... 1)Ť，并计算： u = Cv - A(Bv)。
u 等于 (C-AB)v，因此除了一个元素之外，它将在所有元素中都为零。该元素的索引对应于行索引，其中C与AB不同。元素的价值（a）是非零元素的值 C-AB。
要查找列索引，可以使用向量重复此操作 v2 = (1 2 3 4 ... n)Ť。现在非零元素的值是 ac，哪里 a 是我们之前和之前计算的值 c 是列索引。
由于我们只进行了一些矩阵*向量乘法，因此运行时间为O（n ^ 2）。