O-Notation

Aufrufe: 106     Aktiv: 12.02.2024 um 17:23

0

es seien A∈R^N×N sowie a,b∈R^N für N∈W geben Sie für die folgenden Operationen jeweils deren berechenaufwand in O-Notation an z.B. O(N^2). Dabei seien die für die jeweilige Berechnung notwendigen Voraussetzungen erfüllt. Die Antwort muss nicht begründet werden. a) das Skalarprodukt <a,b> b) die euklidische vektornorm IIxII2 c) das Matrix-Vektor-Produkt A.a d) das Lösen des linearen Gleichungssystems Ax=b mithilfe des Gauß-Algorithmus e) das Zerlegen von A in eine untere Dreiecksmatrix L ∈×∈R N×N und eine obere Dreiecksmatrix R N×N mit =A=L.R f) Das Lösen des linearen Gleichungssystems Ax=b wenn eine Zerlegung aus e) bereits gegeben ist (d.h. L und R sind bereits bestimmt)


meine Lösung/
a) Der Rechenaufwand ist O(N) da jedes Element des einen Vektors mit dem entsprechenden Element des anderen Vektors multipliziert und diese Produkte dann aufsummiert werden.
b) Der Rechenaufwand ist O(N) da jedes Element des Vektors quadriert, diese quadrierten Werte aufsummiert und dann die Quadratwurzel gezogen wird.
c) Der Rechenaufwand ist O(N²) da jede Zeile der Matrix A mit dem Vektor a multipliziert wird, was jeweils NMultiplikationen erfordert, und dies für jede der N �NZeilen der Matrix.
d) Der Rechenaufwand ist O(N³) da mehrere Schritte der Größenordnung durchgeführt werden müssen, um die Matrix auf obere Dreiecksform zu bringen, und dann noch ein Rücksubstitutionsschritt erforderlich ist.
e) Der Rechenaufwand ist O(N³) da dies ähnliche Operationen wie der Gauß-Algorithmus umfasst.
f) Der Rechenaufwand ist O(N²) da zwei sequenzielle Prozesse der Größenordnung N erforderlich sind: einmal für das Vorwärtseinsetzen mit L und einmal für das Rückwärtseinsetzen mit R

 

sind die Richtg ! (die Begründung nur zur Erklärung ob ich richtig bin)

durchgeführt werden müssen, um die Matrix auf obere Dreiecksform zu bringen, und dann noch ein Rücksubstitutionsschritt erforderlich ist.
Diese Frage melden
gefragt

Punkte: 48

 

Es fehlt die Angabe wie Rechenaufwand gezählt wird.   ─   mikn 11.02.2024 um 15:50

a) Das Skalarprodukt zweier Vektoren der Länge N erfordert N Multiplikationen und N-1 Additionen, was linear mit
N skaliert.
b) Länge N erfordert N Quadrierungen und Additionen sowie eine Wurzeloperation, was ebenfalls linear mit
N skaliert
c) Das Matrix-Vektor-Produkt einer NxN Matrix mit einem Vektor der Länge N beinhaltet N Multiplikationen und Additionen für jede der N Zeilen der Matrix.
d) Der Gauß-Algorithmus zum Lösen eines linearen Gleichungssystems umfasst Eliminierungsschritte, die mit der Anzahl der Variablen kubisch wachsen.
e) Die LU-Zerlegung einer NxN Matrix beinhaltet ähnliche Operationen wie der Gauß-Algorithmus und hat daher dieselbe kubische Komplexität.
f) Das Lösen eines linearen Gleichungssystems mit einer bereits durchgeführten LU-Zerlegung beinhaltet das Vorwärtseinsetzen und das Rückwärtseinsetzen, was typischerweise eine quadratische Anzahl von Operationen erfordert.
  ─   abdull 11.02.2024 um 17:51

Das meinte ich nicht. Ich frage meist nach Definitionen. So auch hier. Manchmal wird eine Punkt-Op gezählt, manchmal eine Punkt-Op+1 Add/Subtr.. Außerdem ist unklar, wie und ob die Wurzel-Op gezählt wird.   ─   mikn 11.02.2024 um 18:21

Ich kenne das so, dass der Aufwand für eine Fließkomma-Addition, -Subtraktion, -Division, -Multiplikation und das für Wurzelziehen jeweils 1 ist.
Aufwand zur Adressberechnung, Sprünge, Auswertung von if- und anderen Bedingungen etc. zählen hingegen nicht.
Das ist recht grobschlächtig, aber das ist das O-Kalkül ja auch: O(10 N) = O(N).
  ─   m.simon.539 11.02.2024 um 21:53

Es gibt auch andere Definitionen, daher meine Frage. Ausschlaggebend ist allein das, was beim Frager in der Vorlesung definiert wurde.   ─   mikn 11.02.2024 um 22:05

die Antwort mein Dr. war
https://de.wikipedia.org/wiki/Landau-Symbole#Beispiele_und_Notation
  ─   abdull 12.02.2024 um 16:57

Das war nicht die Frage. Entweder hast Du falsch gefragt, oder "dein Dr." hat die Frage falsch verstanden.   ─   mikn 12.02.2024 um 17:15

Ich hab über die Difin, oder wie kann ich die frage oben lösen !
Die Antwort war wie gezeigt
  ─   abdull 12.02.2024 um 17:23
Kommentar schreiben
0 Antworten