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
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.