Изменения
→Пример работы алгоритма
Выбрав <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>
== Пример работы алгоритма ==
Рассмотрим работу алгоритма на примере перемножения двух матриц <tex> A </tex> и <tex> B </tex>, где
<tex> A = </tex>
<tex>
\left(\begin{array}{cccc}
0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1
\end{array}\right)
</tex>
, <tex> B = </tex>
<tex>
\left(\begin{array}{cccc}
0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1
\end{array}\right)
</tex>
<tex> k = log_2 n = log_2 4 = 2</tex>, то предподсчитаем все скалярные произведения:
== Код алгоритма ==