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

...komplette Frage anzeigen

1 Antwort

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

Hier ist das Bild, die Musterlösung - (Mathematik, Algorithmus, Datenstrukturen)

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).

0
@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!

0
@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.

0

Was möchtest Du wissen?