Даны три матрицы N * N A, B, C. C - это то же самое, что и произведение A и B, за исключением того, что ровно один элемент является неправильным. Наивный алгоритм для его поиска требует N ^ 3 раз. Можем ли мы сделать это быстрее?
Найти один неправильный элемент в матричном продукте?
Ответ 1
Возьмите вектор v = (1 1 1 1 ... 1)T и вычислите: u = Cv - A(Bv).
u равно (C-AB)v, и поэтому он будет иметь нули во всех элементах, кроме одного. Индекс этого элемента соответствует индексу строки, где C отличается от AB. Значение элемента (a) - это значение ненулевого элемента в C-AB.
Чтобы найти индекс столбца, вы можете повторить это с помощью вектора v2 = (1 2 3 4 ... n)T. Теперь значение ненулевого элемента ac, где a - это значение, которое мы рассчитали ранее, и c - индекс столбца.
Поскольку мы выполняем только несколько векторных умножений матрицы *, время работы равно O (n ^ 2).