Изменения
Нет описания правки
== Простое решение ==
Если мы будем считать произведение матриц <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>.
Сейчас будет показано, как немного уменьшить это время.
Теперь, если вместо произведения матриц <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> до <tex dpi=140>O(n^2 \cdot\frac nk) = O(\frac{n^3}{k}) </tex>.
== Оценка трудоёмкости сложности алгоритма и выбор k ==
Оценим трудоёмкость асимптотику данного алгоритма.
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
В силу того, что <tex> \log_4 k </tex> пренебрежительно мал по сравнению с <tex> k </tex> имеем, что <tex> k </tex> с точностью до константы равен <tex> \log n </tex>
Таким образом, при подстановке <tex>k = \log n</tex>, получаем итоговую трудоёмкость асимптотику <tex dpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>
== Код алгоритма ==
<code>
