65
правок
Изменения
м
→Оценка сложности алгоритма и выбор k
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.* Перемножение полученных матриц {{---}} <tex>O(\dfrac{n^3}{k})</tex>.
Итого: <tex>O(2^{2k}k) + O(\dfrac{n^3}{k})</tex>.
