A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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
Nech sú 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í
kde a sú matice typu , pričom z definície násobenia matíc vyplýva, že platí
Štandardný algoritmus možno ekvivalentne prepísať tak, aby násobil matice rekurzívne podľa uvedených vzťahov. Myšlienkou Strassenovho algoritmu je vypočítať hodnoty pomocou iných ekvivalentných vzťahov tak, aby bol počet rekurzívnych volaní násobenia matíc menší (v prípade štandardného algoritmu 8 volaní, v prípade Strassenovho algoritmu len 7 volaní). Pri Strassenovom algoritme sa teda hodnoty počítajú pomocou tzv. Strassenových vzorcov, ktoré obsahujú len 7 násobení matíc typu
kde
Amdalhove pravidlo
Baud
Bloomov filter
Boolova algebra
Cardano (platforma)
Chomského hierarchia
Dijkstrov algoritmus
Eratostenovo sito
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk