Speicherkomplexität

blurry333

Bei rekursiven Funktionen ist es doch ziemlich schwer die Platzkomplexität
zu berechnen. Letztendlich muss man feststellen ob bei der doppelten
Eingabemenge auch der doppelte Speicher benötigt wird. Vielleicht auch der
4fache oder konstant. Wieviel Speicher verbraucht diese Rekursion

funk(unsigned n )
{

  if(n==0) return 4
  else if (n==1) return 5
  else  return funk(n-1)+funk(n-2)+ funk(n-1) / funk(n-2) ; 
}

man muss jetzt irgendwie berechnen wieviel Speicher der Stack verbraucht.
wie ist das z.B. bei der Addition. Er legt den Returnwert von funk(n-1)
auf den Stack. Danach rechnet er funk(n-2) aus. Jetzt kann er ja beide eigentlich addieren und braucht nur noch 1 Speicher. Danach kommt noch die Division . Aber er muss wohl Dividend und Divisor speichern. Hmm schon
sehr komplex. Für den Paramter braucht man wohl auch Speicher.

Die Frage nur was ist wenn sich n verdoppelt. Doppelter Speicher ?

mgaeckler

Wo ist Dein Problem? Die Rekursionstiefe ist in Deinem Fall stets n außer n=0, dann ist die Tiefe 1. D.h. funk wird n-mal gleichzeitig aufgerufen.

Was anderes ist aber die Dauer, diese steigt exponentiell an, da Du bei einem Aufruf funk 4 mal aufrufst, wenn n => 2.

mfg Martin

camper

blurry333 schrieb:

Bei rekursiven Funktionen ist es doch ziemlich schwer die Platzkomplexität
zu berechnen. Letztendlich muss man feststellen ob bei der doppelten
Eingabemenge auch der doppelte Speicher benötigt wird. Vielleicht auch der
4fache oder konstant. Wieviel Speicher verbraucht diese Rekursion
funk(unsigned n )
{

  if(n==0) return 4
  else if (n==1) return 5
  else  return funk(n-1)+funk(n-2)+ funk(n-1) / funk(n-2) ; 
}
man muss jetzt irgendwie berechnen wieviel Speicher der Stack verbraucht.
wie ist das z.B. bei der Addition. Er legt den Returnwert von funk(n-1)
auf den Stack. Danach rechnet er funk(n-2) aus. Jetzt kann er ja beide eigentlich addieren und braucht nur noch 1 Speicher. Danach kommt noch die Division . Aber er muss wohl Dividend und Divisor speichern. Hmm schon
sehr komplex. Für den Paramter braucht man wohl auch Speicher.

Die Frage nur was ist wenn sich n verdoppelt. Doppelter Speicher ?

Eine explizite Antwort gibt der Standard hier nicht, allerdings wissen wir, dass eventuelle Seiteneffekte eines Funktionsaufrufes beim Verlassen einer Funktion abgeschlossen sind. Das indiziert zumindest, dass immer nur die Stackrahmen der unmittelbaren Aufrufer gleichzeitig aktiv sind, der Speicherverbrauch ergibt sich damit als aktuelle_Rekursionsionstiefe * Specherverbrauch_je_Funktionsaufruf. Letzteres muss dann geschätzt werden, wenn nicht mehr über das System bekannt ist.

Konservativ (pesimistisch) geschätzt würde ich 2 Zeiger (Rücksprungadresse+Zeiger auf vorherigen Stackrahmen) + Speicher für evtl. nötige lokale Variablen (sagen wir hier mal 4 ints für die Ergebnisse der Funktionsaufrufe) + den Speicher für den Funktionsparameter + ggf. Speicher für Alignment ansetzen. z.B. bei einem 64bit System: 2*8byte + 4*4byte + 1*4 byte + 12 byte (16-byte alignment) = 48 byte. In der Praxis erwarte ich vom Compiler natürlich bessere Performance.

hustbaer

blurry333 schrieb:

Die Frage nur was ist wenn sich n verdoppelt. Doppelter Speicher ?

Ja, ist in dem Fall O(n).

blurry333

Obwohl die Rekursionstiefe wohl n*4 ist

Nexus

blurry333 schrieb:

Obwohl die Rekursionstiefe wohl n*4 ist

n*4 würde immer noch zur Komplexitätsklasse O(n) gehören, wäre das die Rekursionstiefe.

SeppJ

blurry333 schrieb:

Obwohl die Rekursionstiefe wohl n*4 ist

Nein, wie kommst du auf n*4 als Rekursionstiefe? Bloß weil jeder Funktionsaufruf 4 Rekursionen aufruft sind diese dennoch jeweils nur um 1 tiefer wenn man von n zu n+1 geht. Die Laufzeit wird natürlich um einen Faktor 4 steigen, der Speicherverbrauch nicht.

blurry333

hmm bei n=2 wird funk 4 mal aufgerufen
bei n=3 schon 10 mal .

Fellhuhn

Eher etwas um den Faktor 2.7 herum...

mgaeckler

blurry333 schrieb:

Obwohl die Rekursionstiefe wohl n*4 ist

Liest Du eigentlich nicht alle Antworten.

Ich habe ganz klar geschrieben, die Rekursionstiefe ist n außer n=0.

Martin

SeppJ

blurry333 schrieb:

hmm bei n=2 wird funk 4 mal aufgerufen
bei n=3 schon 10 mal .

Und was hat das mit der Rekursionstiefe zu tun?

void foo(){}

int main()
{
 foo();
 foo();
 foo();
 foo();
 foo();
 foo();
 foo();
}

Hier wird foo() 7x aufgerufen. Wie tief ist die Rekursion? (Tipp: Die Antwort ist nicht 7)

blurry333

hmm

aber:

quicksort()
{

partition ();

quicksort();

quicksort();

}

Was wäre hier die Rekurionstiefe ?

ipsec

blurry333 schrieb:

hmm

aber:
quicksort()
{

partition ();

quicksort();

quicksort();

}
Was wäre hier die Rekurionstiefe ?

Unendlich, wenn partition nicht irgendwann ne Exception wirft.

volkard

blurry333 schrieb:

hmm
aber:
quicksort()
{
  partition ();
  quicksort();
  quicksort();
}
Was wäre hier die Rekurionstiefe ?

Schlimmstenfalls n, wenn n die Arraygröße ist. Deswegen soll man so ein quicksort auch nicht machen.
Zum Glück gibt es einfache Abhilfe. Zum Beispiel so:

quicksort()
{
  partition ();
  quicksort(kleinerenTeil);
  quicksort(groesserenTeil);//tail recursion noch schnell zur schleife machen
}

Damit ist die Tiefe schlimmstenfalls log(n), weil schlimmstenfalls in ein halb so großes Array abgestiegen wird. Und alles ist gut.

mgaeckler

blurry333 schrieb:

hmm

aber:
quicksort()
{

partition ();

quicksort();

quicksort();

}
Was wäre hier die Rekurionstiefe ?

Das hängt davon ab, wie groß der Stack werden darf. Wenn das 2 GB ist, der Stack vor dem ersten Aufruf von quicksort leer ist und jeder Aufruf 4 Byte auf dem Stack belegt, dann kracht es bei einer Rekursionstiefe von 536870912.

mfg Martin

mgaeckler

ipsec schrieb:

Unendlich, wenn partition nicht irgendwann ne Exception wirft.

Dazu brauchst Du aber einen unendlichen Computer. Da das Weltall jedoch endlich ist, kann es sowas nicht geben.

mfg Martin

ipsec

mgaeckler schrieb:

Dazu brauchst Du aber einen unendlichen Computer. Da das Weltall jedoch endlich ist, kann es sowas nicht geben.

Selbst eine Turing-Maschine hat ein unendliches Band. Die Frage spielt doch auf eine theoretische Betrachtung ab. Oder soll der TE fortan bei jeder Frage nach der Rekursionstiefe als Antwort 1 geben, weil er von einem System ausgehen muss, dessen Stack mit 4 Byte Größe nur einen Funktionsaufruf aufnehmen kann?

mgaeckler

ipsec schrieb:

mgaeckler schrieb:

Dazu brauchst Du aber einen unendlichen Computer. Da das Weltall jedoch endlich ist, kann es sowas nicht geben.

Selbst eine Turing-Maschine hat ein unendliches Band. Die Frage spielt doch auf eine theoretische Betrachtung ab. Oder soll der TE fortan bei jeder Frage nach der Rekursionstiefe als Antwort 1 geben, weil er von einem System ausgehen muss, dessen Stack mit 4 Byte Größe nur einen Funktionsaufruf aufnehmen kann?

In der Theorie mag die Turingmaschine ein unendliches Band haben. Reale Implementierungen können das aber nicht haben.

Das Quicksortbeispiel vom Threadstrater hatte kein Abbruchkriterium. Die Rekursion läuft daher so lange bis der Stack voll ist. Dann kracht es eben.

mfg Martin

ipsec

Natürlich. Aber die Frage nach der Rekursionstiefe eines Algorithmus ist ja sehr theoretischer Natur, weshalb man m.E. schon von einem theoretischem Computer mit unendlichem Stack ausgehen kann (vor allem da der Algorithmus erstmal völlig unabhängig vom System ist). Und rein formal ist - so sehe ich das - die Rekursionstiefe von x() { x(); } unendlich und nicht 53,7 Mrd.