Laufzeit von Matrizenmultiplikation

20.10.2019, 00:12	MaPalui	Auf diesen Beitrag antworten »
Laufzeit von Matrizenmultiplikation Hallo Leute mich beschäftigt gerade die Frage nach der Laufzeit naiver Matrizenmultiplikation. Mein Ansatz dazu: Multiplizieren wir zwei Matrizen, A und B, und seien $\begin{eqnarray} A\in\mathbb K^{m\times n}, B\in\mathbb K^{n\times o} \end{eqnarray}$ . Ein einzelnes Skalarprodukt kostet mich hier $\begin{eqnarray} n \end{eqnarray}$ Multiplikationen und ich muss $\begin{eqnarray} n-1 \end{eqnarray}$ mal aufaddieren. Insgesamt muss ich dies $\begin{eqnarray} m\cdot o \end{eqnarray}$ mal machen. Mein Ergebnis ist also $\begin{eqnarray} \mathcal{O}(n \cdot (n-1)\cdot m\cdot o) = \mathcal{O}(n^2\cdot m \cdot o) \end{eqnarray}$ ist das ok?
20.10.2019, 13:54	URL	Auf diesen Beitrag antworten »
RE: Laufzeit von Matrizenmultiplikation Wie kommst du denn auf zwei Multiplikation? Ich komme auf n für ein Skalarprodukt.
20.10.2019, 14:54	MaPalui	Auf diesen Beitrag antworten »
Oooooooooh nein Ich hatte vorher $\begin{eqnarray} n^2 \end{eqnarray}$ dort stehen und natürlich genau den falschen Teil davon gelöscht... Es sollten also n Multiplikationen sein. Nochmal Edit: Ich habe es oben verbessert, aber meine neue Version schreibe ich jetzt hier, sonst geht das durcheinander. ich brauche n Multiplikationen und (n-1) Additionen. Das ganze passiert $\begin{eqnarray} m\cdot o \end{eqnarray}$ mal. Insgesamt also $\begin{eqnarray} (n+(n-1))\cdot m\cdot o \end{eqnarray}$ Operationen, also $\begin{eqnarray} \mathcal{O}(nmo) \end{eqnarray}$
20.10.2019, 14:58	URL	Auf diesen Beitrag antworten »
Sieht für mich richtig aus
20.10.2019, 15:00	MaPalui	Auf diesen Beitrag antworten »
Super, danke :-* Eine Frage habe ich zur Komplexität noch. Ich weiß ja nun, dass ich genau $\begin{eqnarray} n(n-1)mo \end{eqnarray}$ Operationen brauche. Wenn ich das nun als $\begin{eqnarray} \mathcal{O}(nmo) \end{eqnarray}$ schreibe, verliere ich dann nicht die Genauigkeit?
20.10.2019, 15:02	URL	Auf diesen Beitrag antworten »
Da fehlen ein Pluszeichen und Klammern. Wenn du von einem exakten Term zur Größenordnung übergehst, verlierst du doch immer Information. Welche Genauigkeit meinst du denn darüber hinaus zu verlieren?
Anzeige

20.10.2019, 15:05	MaPalui	Auf diesen Beitrag antworten »
Oh ja richtig, danke Also ich tue mir immernoch schwer mit der Landau-Notation. Wenn ich doch die genau Anzahl an Operationen kenne, warum soll ich dann noch die Landaunotation nutze, die mir doch eben nicht genau sagt, wieviele Operationen ich brauche. In unserem Beispiel weiß ich ja, wieviele ich brauche. Wenn ich jetzt nur $\begin{eqnarray} \mathcal{O}(nmo) \end{eqnarray}$ gegeben hätte, könnten es ja auch 10.000 mal soviele sein
20.10.2019, 15:11	URL	Auf diesen Beitrag antworten »
Hier kannst du die Anzahl exakt angeben, aber oft genug man es eben nicht. Da ist es angenehm, wenn man die Größenordnung von Algorithmen vergleichen kann, um zu sehen, ob man eine gute Idee hatte oder das alles im Vergleich mit etablierten Verfahren viel zu aufwändig ist.
20.10.2019, 15:13	MaPalui	Auf diesen Beitrag antworten »
Ok, danke sehr! Verwundert mich immer wieder wenn man sich in der Mathematik mit "weniger" zufrieden gibt

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »