Portál:Matematika/Odporúčaný článok/30

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

Strassenov algoritmus, pomenovaný podľa Volkera Strassena, je algoritmus na násobenie matíc. Oproti štandardnému algoritmu násobiacemu matice priamo podľa vzťahu z definície, s časovou zložitosťou , má Strassenov algoritmus o niečo lepšiu asymptotickú časovú zložitosť , čo znamená, že pre veľké matice je Strassenov algoritmus rýchlejší, než štandardný algoritmus.

Strassenov algoritmus nie je asymptoticky optimálny. Najrýchlejší známy algoritmus násobenia matíc, tzv. Coppersmithov–Winogradov algoritmus, má časovú zložitosť približne , ale vzhľadom na veľmi veľký konštantný faktor sa táto výhoda prejaví len pre extrémne veľké matice.

Algoritmus[upraviť zdroj]

Nech matice typu (v prípade, že matice nie sú typu , je možné doplniť chýbajúce riadky a stĺpce nulami) nad okruhom . Označme súčin týchto matíc. Potom platí

Celý článok...