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

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

Текущая версия от 13:44, 18 ноября 2010

Алгоритм Штрассена (V.Strassen, 1968) — алгоритм умножения двух [math]\displaystyle{ (2 \times 2) }[/math]-матриц с элементами из произвольного кольца, в котором достаточно семи умножений. Рекурсивно применяя этот метод, можно умножить две [math]\displaystyle{ (n \times n) }[/math]-матрицы за время [math]\displaystyle{ O(n^{\log 7}) }[/math].

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.