403
правки
Изменения
м
Состоящие состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.»
Хочется <s>большего</s> меньшего..Сейчас будет показано, как немного уменьшить это время.
В прошлом Воспользуемся полученным в предыдущем пункте была посчитана какая-то непонятная муть. Вот сейчас-то мы ей и воспользуемсярезультатом.
minor fixes
Рассмотрим следующую задачу: «Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,
== Простое решение ==
Если мы будем считать произведение матриц <tex>C = A \cdot B</tex> по определению(<tex dpi=140>c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}</tex>), то трудоёмкость алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из <tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, пропорциональное <tex>n</tex>.
== Предподсчёт ==
Воспользуемся следующим {{TODO|t=ну не уместно здесь это словосочетание}} финтом ушамиприёмом. Возьмём некоторое целое число <tex>k</tex>. Для всех возможных пар двоичных векторов длины <tex>k</tex> подсчитаем и запомним их скалярное произведение по модулю <tex>2</tex>.
== Сжатие матриц ==
Возьмём первую матрицу. разделим каждую её строку на куски размера <tex>k</tex>. В каждый кусок запишем Для каждого куска определим номер двоичного вектора, который соответствует числам, которые находятся находящимся на этом куске. Если кусок получился неравным по длине <tex>k</tex>(последний кусок строки), то будем считать, что в конце в нём в конце идут не влияющие на умножение нули. Получим матрицу <tex dpi=140>A'_{n \times \lceil\frac{n}{k} \rceil}</tex>.
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</tex>.
Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \frac nk \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <texdpi=140>O(n^2 \cdot\frac nk) = O(\frac{n^3}{k}) </tex>.
== Оценка трудоёмкости и выбор k ==
Итого: <tex>O(2^{2k}k) + O(\frac{n^3}{k})</tex>.
Взяв <tex>k = \log n</tex>, получаем итоговую трудоёмкость <texdpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>
