Aufgabe - Matrixmultiplikation
Großartige Neuigkeiten: Die Brüder Tick, Trick und Track haben durch intensives Studium des Strassen-Algorithmus jeweils eine Variante gefunden, um zwei k x k-Matrizen mitt weniger als \( k^3 \) Multiplikationen zu multiplizieren. Tick ist es gelungen zu zeigen, wie man 19 x 19-Matrizen mit nur 3333,333 Multiplikationen lösen kann. Trick schafft \( 27 \times 27 \) -Matrizen mit nur 11111,111 Multiplikationen. Track ist schließlich in der Lage, \( 42 \times 42 \) -Matrizen mit nur 4222,242 Multiplikationen zu lösen.
Beurteilen Sie, welcher der drei so entstehenden Divide-and-Conquer-Algorithmen die beste asymptotische Laufzeit besitzt. Welche der Verfahren haben eine bessere asymptotische Laufzeit als der Strassen-Algorithmus?
Hinweis: Sie müssen den Rechenweg nur für einen der Brüder vollstandig angeben. Bei den anderen dürfen Sie sich auf das Ergebnis beschränken.
Wie genau soll ich denn das Master-Theorem anwenden? In der Musterlösung steht, dass man durch das Master-Theorem auf die Laufzeiten kommt.
