Sie sind aktuell nicht angemeldet.

Funktionen: Einloggen  |  Neu registrieren  |  Suchen

Re: HILFE: Sortierung: Nicht genügend Stapelspeicher!
Autor: Preisser
Datum: 19.05.10 16:54
Hi, Laut Wikipedia benötigt der QuickSort im ungünstigsten Fall einen Stapelspeicher, der linear zur Anzahl (n) der zu sortierenden Elemente wächst (O(n), mit Rekursionstiefe n). Ein Stapelüberlauf tritt auf, wenn die Rekursionstiefe so hoch ist, dass auf dem vom System zugewiesenen Stack kein Platz mehr ist (bei jedem rekursiven Aufruf der Sortierfunktion muss ein neuer Frame auf dem Stack angelegt werden, der genügend Platz hat, um alle in der Funktion deklarierten Variablen unterzubringen). Du müsstest deshalb deinen Algorithmus so optimieren, dass die Rekursionstiefe kleiner ist (z. B. mit Endrekursionsbeseitigung, dort beträgt die Rekursionstiefe nur noch log(n), der benötigte Stapelspeicher wächst also nur noch logarithmisch zur Listenlänge). Beitrag wurde zuletzt am 19.05.10 um 17:03:10 editiert.

HILFE: Sortierung: Nicht genügend Stapelspeicher!	1.533	Fenerlisivas	19.05.10 08:43
Re: HILFE: Sortierung: Nicht genügend Stapelspeicher!	1.060	Preisser	19.05.10 16:54
Re: HILFE: Sortierung: Nicht genügend Stapelspeicher!	1.045	icetea123	19.05.10 18:40

Sie sind nicht angemeldet! Um auf diesen Beitrag zu antworten oder neue Beiträge schreiben zu können, müssen Sie sich zunächst anmelden. Einloggen  |  Neu registrieren

Funktionen:  Zum Thema  |  Gesamtübersicht

Suchen