Strassen-Algorithmus zur Analyse der Matrixmultiplikationskomplexität

8

Ich sehe überall, dass die rekursive Gleichung für die Komplexität von Strassen alg lautet: Das ist mir nicht so klar. Der Parameter soll die Größe der Eingabe sein, aber es scheint, dass es sich hier um eine Dimension einer Matrix handelt, während die Eingabegröße tatsächlich . Außerdem ist jede Matrix der Eingabe in 4 Untermatrizen unterteilt, so dass es den Anschein hat, dass die rekursive Gleichung

T(n)=7T(n2)+O(n2).
nn2
T(n)=7T(n4)+O(n).

dafnahaktana
quelle

Antworten:

13

Es ist wahr, dass der Parameter normalerweise die Größe der Eingabe angibt, aber dies ist nicht immer der Fall. Bei der Quadratmatrixmultiplikation bezeichnet die Anzahl der Zeilen (oder Spalten). Bei Graphen bezeichnet häufig die Anzahl der Eckpunkte und die Anzahl der Kanten. Für Algorithmen für Boolesche Funktionen bezeichnet die Anzahl der Eingaben, obwohl die Wahrheitstabelle selbst die Größe . Es gibt viele andere Beispiele.nnnmn2n

Yuval Filmus
quelle
5

n×nT(n)n×nn2×n2T(n2)

Oh mein Gott
quelle
0

Die zeitliche Komplexität basiert häufig auf der Eingabegröße, ist jedoch keine absolute Anforderung. In diesem Fall erscheint es für die Multiplikation von nxn-Matrizen am natürlichsten, die Anzahl der Operationen basierend auf n und nicht auf der Problemgröße nx n zu zählen.

gnasher729
quelle