Алгоритм Штрассена: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Алгоритм Штрассена''' (''V.Strassen, 1968'') - алгоритм умножения двух <math>(2 \times 2)</math>...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман] | [Ахо-Хопкрофт-Ульман] | ||
Версия от 13:00, 25 сентября 2009
Алгоритм Штрассена (V.Strassen, 1968) - алгоритм умножения двух [math]\displaystyle{ (2 \times 2) }[/math]-матриц с элементами из произвольного кольца, в котором достаточно семи умножений. Рекурсивно применяя этот метод, можно умножить две [math]\displaystyle{ (n \times n) }[/math]-матрицы за время [math]\displaystyle{ O(n^{\log 7}) }[/math].
Литература
[Ахо-Хопкрофт-Ульман]