Frage von BillHatayu, 89

Algorithmen - Zeitkomplexität/Speicherkomplexität berechnen - Wer weiß weiter?

In der Lösung (siehe Bild) steht "siehe Vorlesung", aber im Skript steht nichts hilfreiches.

Vielleicht kann mir jemand den Rechenweg dazu erklären, wie man auf 1. Zeitkomplexität und 2. Speicherkomplexität kommt...

Dafür wäre ich euch sehr dankbar!

Antwort
von BillHatayu, 87

Habe vergessen das Bild hinzuzufügen, hier ist die Musterlösung...

Kommentar von BillHatayu ,

Also zur Zeitkomplexität habe ich denke ich einen Ansatz gefunden.

Die rekursive Funktion ruft sich ja immer wieder selber auf.

Wenn man am Beispiel n=4 die Aufrufe zählt, sind es 8 Funktionsaufrufe.

8=2^3 (zwei hoch drei)

Für n=4: Die Funktion ist also langsamer als 2^n=2^4=16 und schneller als 2^n/2=2^2=2

Jetzt muss ich eine Aussage über die Zeitkomplexität machen.

Die Funktion ist langsamer oder höchstens so schnell wie 2^n (zwei hoch n), daraus folgt T(n) ist Element der Menge O(2^n).

Die Funktion ist gleich schnell oder schneller als 2^(n/2), daraus folgt T(n) ist Element der Menge Ω(2^(n/2))  (Omega 2 hoch n-halbe).

Kommentar von BillHatayu ,

Meine Spekulationen zur Speicherkomplexität (Das Skript und die Lösung sind ein Witz, im gesamten Skript taucht nicht einmal das Wort "Speicherkomplexität" auf):

Bei der rekursiven Funktion T1 braucht es im Vergleich zu n höchstens n Speicherplätze. Die Speicherplätze verhalten sich also linear zu n. Warum das so ist, ist mir schleierhaft, weil die Funktion sich ja selbst aufruft und exponentiell ist. Also sollte doch der Speicherbedarf auch exponentiell sein. Oder konstant, wenn der alte Speicher immer wieder überschrieben wird... Aber wieso linear zu n??

Bei der iterativen Funktion ist es etwas klarer. 
Der Speicherbedarf ist linear, weil die Schleife vereinfacht von n bis 0 runterzählt und die Ergebnisse in einem Array/einer Liste speichert.

Für weitere Ergänzungen wäre ich sehr dankbar!

Kommentar von BillHatayu ,

Aha, ich vermute jetzt, der Speicherbedarf ist linear zu n, weil das Ergebnis für jedes n in einem Stack abgespeichert wird, linear zu n. Quasi durch den return-Wert. Anders kann es zumindest nicht sein.

Keine passende Antwort gefunden?

Fragen Sie die Community