Informatiker Board | Praktische Informatik | Gauss Elimination

Informatiker Board » Themengebiete » Praktische Informatik » Gauss Elimination » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge

eulerscheZahl

code:

1:
2:
3:
4:

for (k = 0; k < n - 1; k = k + 1) //und nochmal abhängig von n
for (i = k + 1; i < n; i = i + 1) //auch abhängig von n
for (j = k + 1; j < n; j = j + 1) //hier sind wir abhängig von n
a[i][j] = a[i][j] - a[i][k] * a[k][j] / a[k][k]; //der Teil ist konstant

Es wird also 3 Mal bis n gezählt (bei den inneren Schleifen im Mittel geweils bis n/2, aber die 0.5 ist nur ein Faktor und interessiert nicht).
Macht O(n*n*n) = O(n^3)

aber bei der b) muss die Laufzeit doch auch von a abhängig sein, schließlich ist a für den Abbruch der Rekursion verantwortlich.

kleinerstrolch

Gauss Elimination

a) Gauss-Elimination:
for (k = 0; k < n - 1; k = k + 1)
for (i = k + 1; i < n; i = i + 1)
for (j = k + 1; j < n; j = j + 1)
a[i][j] = a[i][j] - a[i][k] * a[k][j] / a[k][k];
Die Berechnung innerhalb der innersten Schleife ist von den Werten der Schleifenzahler unabh ¨ angig, ¨
d.h. benotigt eine konstante Zeit ¨ tg. Wie ist die algorithmische Komplexitat in Abh ¨ angigkeit von ¨ n?
(2 Punkte)
b) Rekursiver Funktionsaufruf:
int f (int a, int b) {
if (a >= b)
return g(a);
else
return f(a, b - 1) + f(a + 1, b);
};
Uberlegen Sie zuerst, welche Gr ¨ oße als Komplexit ¨ atsparameter sinnvoll ist! Die Zeit, um ¨ g(a) auszurechnen,
soll vom Wert von a unabhangig sein. Wie ist die algorithmische Komplexit ¨ at? (3 Punkte)

Bräuchte bei dieser Aufgabe ein klein wenig Hilfe beim verstehen und Lösungserarbeiten.
Mit einem Komillitonen zusammen kam bei der a) als Lösung irgendwie

O(n log n)

obwohl ich nicht weiss ob das stimmt und wie er darauf kam wurde mir auch nach einigen erklärungen schlichtweg nicht ersichtlich.

und zu der b haben wir als ansatz:

"Da ersichtlich ist das die funktion sich 2 mal selbst aufrufen kann und diese wiederum auch 2 mal aufrufbar ist -> O(2^b)2"

stimmen diese Lösungen so? Wenn ja - warum verwirrt

bei a zumindest)