Frage von Kvanilli, 17

Matritzenmultiplikation Standardalgorthmus?

Ich habe eine Verständnisfrage zur Matritzenmultiplikation. Und zwar kann man diese wie folgt in einem Pseudocode implementieren:

function matmult(A,B,l,m,n)

C = zeroes(l,n)
for i = 1 to l
for k = 1 to n
for j = 1 to m
C(i,k) = C(i,k) + A(i,j) * B(j,k)

end

end

end

return C ______________________

Nun zu meiner eigentlichen Frage. Wie erklärt sich die Anzahl der benötigten Operatoren von der Ordnung: O(l x m x n) ?? Und wieviele Zuweisungen hat dieser Algorithmus für Summe von A(i,j) * B(j,k) also wie lässt sich das berechnen. (klar mit der Formel, aber wie definiert sich die Formel am Bsp. des Pseudocodes?) (siehe Wikipedia https://de.wikipedia.org/wiki/Matrizenmultiplikation)

Antwort
von Melvissimo, 6

kurz gesagt: Du hast 3 verschachtelte unabhängige Schleifen, an deren Ende immer eine konstante Anzahl an Operationen durchgeführt wird. Dann ist die Anzahl der benötigten Operationen O(s1 * s2 * s3), wobei s1 z.B. für die Anzahl der Durchläufe von Schleife 1 steht.

Für die Berechnung von C(i,k) musst du offensichtlich alle A(i,j) * B(j,k) aufaddieren. Da es m mögliche Kandidaten für "j" gibt (das ist ja gerade der Laufindex der Summe), sind das auch m Zuweisungen.

Keine passende Antwort gefunden?

Fragen Sie die Community