0 Daumen
527 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
0 Antworten
0 Daumen
0 Antworten
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community