Аноним

Алгоритм Штрассена: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Алгоритм Штрассена''' (''V.Strassen, 1968'') - алгоритм умножения двух <math>(2 \times 2)</math>...)
 
Нет описания правки
Строка 1: Строка 1:
'''Алгоритм Штрассена''' (''V.Strassen, 1968'') -  
'''Алгоритм Штрассена''' (''[[V.Strassen|V.Strassen]], 1968'') - [[алгоритм|алгоритм]] умножения двух <math>(2 \times 2)</math>-матриц с элементами из произвольного кольца, в котором достаточно семи умножений. Рекурсивно применяя этот метод, можно умножить две <math>(n \times n)</math>-матрицы за время <math>O(n^{\log 7})</math>.
алгоритм умножения двух <math>(2 \times 2)</math>-матриц с элементами из
произвольного кольца, в котором достаточно семи умножений. Рекурсивно
применяя этот метод, можно умножить две <math>(n \times n)</math>-матрицы за
время <math>{\cal O}(n^{\log 7})</math>.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман]
[Ахо-Хопкрофт-Ульман]