Informatiker Board | Praktische Informatik

Informatiker Board » Themengebiete » Praktische Informatik » Gauss Elimination

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Gauss Elimination

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

kleinerstrolch
Grünschnabel

Dabei seit: 08.01.2015
Beiträge: 8

Gauss Elimination

Zitatantwort auf diesen Beitrag erstellen

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)

13.01.2015 19:49

Nehmen Sie kleinerstrolch in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 14.01.2015 06:47.

14.01.2015 05:49

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Gauss Elimination