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

Алгоритм получает на вход две булевы матрицы ${\displaystyle (n\times n)}$ ${\displaystyle A}$ и ${\displaystyle B}$ и возвращает матрицу ${\displaystyle C=AB}$.

Пусть ${\displaystyle m=\lfloor \log n\rfloor }$.

Разобьём ${\displaystyle A}$ на матрицы ${\displaystyle A_{1},A_{2},...,A_{\lceil n/m\rceil }}$, где ${\displaystyle A_{i},1\leq i<\lceil n/m\rceil }$, состоит из столбцов матрицы ${\displaystyle A}$ с номерами от ${\displaystyle m(i-1)+1}$ до ${\displaystyle mi}$, а ${\displaystyle A_{\lceil }n/m\rceil }$ — из оставшихся столбцов, к которым добавлены столбцы нулей, если это нужно, чтобы в матрице было ${\displaystyle m}$ столбцов.

Разобьём ${\displaystyle B}$ на матрицы ${\displaystyle B_{1},B_{2},...,B_{\lceil n/m\rceil }}$, где ${\displaystyle B_{i},1\leq i<\lceil n/m\rceil }$, состоит из строк матрицы ${\displaystyle B}$ с номерами от ${\displaystyle m(i-1)+1}$ до ${\displaystyle mi}$, а ${\displaystyle B_{\lceil }n/m\rceil }$ — из оставшихся строк, к которым добавлены строки нулей, если это нужно, чтобы в матрице было ${\displaystyle m}$ строк.

begin

  for ${\displaystyle i\leftarrow 1}$ to ${\displaystyle \lceil n/m\rceil }$ do

  begin

    comment Вычисляем суммы строк ${\displaystyle b_{1}^{(i)},...,b_{m}^{(i)}}$ матрицы ${\displaystyle B_{i}}$;

    СУММАСТРОК[${\displaystyle 0}$] ${\displaystyle \leftarrow \underbrace {[0,0,\cdots ,0]} _{n}}$

    for ${\displaystyle j\leftarrow 1}$ to ${\displaystyle 2^{m}-1}$ do

    begin

      Пусть ${\displaystyle k}$ таково, что ${\displaystyle 2^{k}\leq j<2^{k+1}}$

      СУММАСТРОК[${\displaystyle j}$]${\displaystyle \leftarrow }$СУММАСТРОК[${\displaystyle j-2^{k}}$]${\displaystyle +b_{k+1}^{(i)}}$

    end

    Пусть ${\displaystyle C_{i}}$ — матрица,  i-я строка которой равна СУММАСТРОК[ЧИС(${\displaystyle a_{j}}$)],

    где ${\displaystyle a_{j}}$ — j-я строка матрицы ${\displaystyle A_{i}}$, ${\displaystyle 1\leq j<n}$,

  end;

  Пусть ${\displaystyle C=\sum _{i=1}^{\lceil n/m\rceil }C_{i}}$

end.[2]

ЧИС(v) — целое число, представленное двоичным вектором v, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС([0,1,1])=6.

Простая индукция по ${\displaystyle j}$ показывает, что СУММАСТРОК[${\displaystyle j}$] становится равной поразрядной булевой сумме таких строк ${\displaystyle b_{k}}$ матрицы ${\displaystyle B_{i}}$, что в двоичном представлении числа ${\displaystyle j}$ на ${\displaystyle k}$-том месте справа стоит 1. Отсюда вытекает, что ${\displaystyle C_{i}=A_{i}B_{i}}$ и ${\displaystyle C=AB}$.

Рассмотрим цикл по ${\displaystyle j}$. Вычисление и присваивание значений СУММАСТРОК[${\displaystyle j}$] происходит за ${\displaystyle O(n)}$. Вычисление ${\displaystyle k}$ занимает время ${\displaystyle O(m)}$. Итерация цикла выполняется за ${\displaystyle O(n)}$, всего ${\displaystyle 2^{m}-1}$ итераций. ${\displaystyle m<\log n}$, ${\displaystyle 2^{m}-1<n}$, следовательно весь цикл выполнится за ${\displaystyle O((2^{m}-1)n)=O(n^{2})}$.

Вычисление ЧИС(${\displaystyle a_{j}}$) имеет сложность ${\displaystyle O(m)}$, а копирование вектора СУММАСТРОК[ЧИС(${\displaystyle a_{j}}$)] — сложность ${\displaystyle O(n)}$, так что инициализация ${\displaystyle C_{i}}$ выполняется за ${\displaystyle O(n^{2})}$. Итого, цикл по ${\displaystyle i}$ выполняется за ${\displaystyle O(n^{2})}$. Всего ${\displaystyle \lceil n/m\rceil }$ итераций. ${\displaystyle \lceil n/m\rceil <2n/\log n}$, следовательно сложность цикла — ${\displaystyle O(n^{3}/\log n)}$.

Сумма ${\displaystyle C_{i}}$ вычисляется за ${\displaystyle O(n^{2}*\lceil n/m\rceil )=O(n^{3}/\log n)}$.

Итоговая сложность алгоритма — ${\displaystyle O(n^{3}/\log n)}$.