Speicherkomplexität

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.