Lexikon der Mathematik: sublinearer Platz
Schranken für die Raumkomplexität, die langsamer als n wachsen.
Da Platz n für die Eingabe benötigt wird, und die Ausgabe länger als n sein kann, wird für die Betrachtung von sublinearem Platz davon ausgegangen, daß die Turing-Maschine auf dem Eingabeband nicht schreiben und auf dem Ausgabeband nicht lesen darf. Für den Speicherplatzbedarf wird dann nur das Arbeitsband berücksichtigt.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!