Informatik - Speicherkomplexität von Algorithmen - Wieso ist der Speicherbedarf linear zu n, also O(n)?

... komplette Frage anzeigen

2 Antworten

Der Speicherbedarf korreliert mit der Rekursionstiefe - bei jedem Aufruf wird mindestens der übergebene Parameter und die Rückkehradresse gespeichert.

Die Rekursionstiefe ist identisch mit der Nummer der gewünschten Fibonacci-Zahl.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von BillHatayu
04.06.2016, 15:19

Ist die Rekursionstiefe das selbe, wie die Zeitkomplexität? Also für dieses Beispiel 2^n-1?

Wie komme ich allgemein zur Rekursionstiefe? Die Rekursionstiefe ist die Anzahl der Funktionsaufrufe, oder? 
Ich dachte die Funktion ruft sich exponentiell oft auf, also 2^n-1. 
Für n=4 ruft sie sich 8 mal auf...


Du sagst, die Rekursionstiefe ist identisch mit der Nummer der gewünschten Fibonacci-Zahl. Also ist die Rekursionstiefe z.B. 4 für n=4 ? Das würde erklären, wiese es O(n) ist, aber ich verstehe es noch nicht...
Danke schon mal für deine Antwort. Kannst du versuchen, es etwas einfacher und genauer zu erklären? Vielen Dank

0

Bei jedem rekursiven Aufruf der Funktion wird z.B. die Variable anz. neu angelegt.

Das und der Funktionsaufruf selbst brauchen Speicher, welcher demnach n mal benötigt wird.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von BillHatayu
04.06.2016, 15:23

Wenn ich die Funktionsaufrufe für n=4 zähle, komme ich aber auf 8 Funktionsaufrufe. Das verstehe ich nicht. Dann muss doch der Speicherbedarf auch exponentiell sein, also O(n^2) und nicht O(n)...

1