Изменения

Перейти к: навигация, поиск

Метод четырёх русских для умножения матриц

4 байта добавлено, 23:42, 8 января 2017
м
Оценка сложности алгоритма и выбор k
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>
* Перемножение полученных матриц {{---}} <tex dpi=140>O(\fracdfrac{n^3}{k})</tex>
Итого: <tex>O(2^{2k}k) + O(\fracdfrac{n^3}{k})</tex>.Выбрав <tex>k = \log n </tex>, получаем требуемую асимптотику <tex dpi=140>O(n^2 \log n) + O(\fracdfrac{n^3}{\log n}) = O(\fracdfrac{n^3}{\log n})</tex>
== Пример работы алгоритма ==
65
правок

Навигация