Gauss Elimination

13.01.2015, 19:49

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)

14.01.2015, 05:49

Auf diesen Beitrag antworten »

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.

Neue Frage »

Antworten »

Gauss Elimination

Verwandte Themen