Алгоритм четырёх русских

---

Алгоритм четырёх русских — в информатике представляет собой метод ускорения алгоритмов с использованием булевых матриц или, в более общем смысле, алгоритмов с использованием матриц, в которых каждая ячейка может принимать только ограниченное число возможных значений.

Разработанный комбинаторный алгоритм позволяет умножать матрицы за ${\displaystyle O(n^{3}/\log n)}$. С некоторыми изменениями можно получить время работы ${\displaystyle O(n^{3}/\log ^{2}n)}$. В 2015 году был получен алгоритм, работающий за ${\displaystyle {\hat {O}}(n^{3}/\log ^{4}n)}$.^[1]

Основная идея метода состоит в том, чтобы разделить матрицу на небольшие квадратные блоки размером ${\displaystyle t\times t}$ для некоторого параметра ${\displaystyle t}$ и использовать таблицу поиска для быстрого выполнения алгоритма в каждом блоке. Индекс в таблице поиска кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а значения в таблице поиска кодируют значения граничных ячеек в правом нижнем углу блока после операции. Таким образом, общий алгоритм может быть выполнен с использованием только ${\displaystyle (n/t)^{2}}$ блоков вместо ${\displaystyle n^{2}}$ ячеек матрицы, где ${\displaystyle n}$ — длина строки матрицы. Для того чтобы размер таблиц поиска (и время, необходимое для их инициализации) было достаточно малым, ${\displaystyle t}$ обычно выбирается равным ${\displaystyle O(\log n)}$.

---