В інформатиці, метод чотирьох росіян— це техніка пришвидшення алгоритму, що використовує булеві матриці або, загальніше, алгоритмів, що використовують матриці в яких кожна комірка може набувати обмеженої кількості можливих значень.
Розроблений комбінаторний алгоритм дозволяв множити булеві матриці за . З маленькою зміною алгоритм може працювати за . Станом на 2015 було вже отримано алгоритм, що працює за .
Алгоритм
Нехай і будуть булевими матрицями. Обираючи довільне можна розбити на блоки розміру . Позначимо кожен такий блок через , тоді .
Для кожної двійки створюємо таблицю пошуку згідно з такою специфікацією: для кожного бітового вектора завдовжки : . Маємо, що .
Час необхідний для обчислення всіх таблиць асимптотично становить: , бо всього двійок , векторів і обчислення потребує для сталої .
Щодо матриці , то кожен її стовпчик можна розбити на частин. Нехай буде й шматок го стовпчика. Кожен добуток можна обчислити за сталий час, бо ми вже маємо обчислені таблиці.
Щоб обчислити , можна зробити наступне.
Для : (за означенням булевого добутку матриць). Таким чином, час потрібний для виконання алгоритму становить .
Передобчисливши всі можливі побітові у таблицю так, що , де , можна зменшити час виконання до .
Історія
Алгоритм запропонували Арлазаров, Дініц, Кронрод і Фараджев в 1970. Походження назви невідоме; пояснюють: Другий метод, часто згадуваний як алгоритм «чотирьох росіян», через кількість і громадянство його винахідників, що «практичніше» ніж алгоритм в теоремі 6.9. Всі чотири автори працювали тоді в Москві.Приналежність авторів .
Примітки
. Оригінальна назва: "Об экономном построении транзитивного замыкания ориентированного графа".