Unter der Platzkomplexität eines Problems versteht man den (minimalen) Bedarf an Speicherplatz eines Algorithmus zur Lösung dieses Problems, in Abhängigkeit von der Länge der Eingabe.
Es interessiert also nicht der Speicherbedarf eines konkreten Programms auf einem bestimmten Computer, sondern vielmehr, wie der Speicheraufwand wächst, wenn mehr Daten zu verarbeiten sind. Beispielsweise beantwortet die Platzkomplexität die Frage, ob sich der benötigte Speicher bei doppelter Eingabe-Datenmenge verdoppelt oder quadriert (siehe auch Skalierbarkeit). Sie wird deshalb auch Speicherkomplexität genannt.
Die Platzkomplexität wird immer in Bezug auf ein Maschinenmodell angegeben. In der Regel ist das Bezugsmodell die Turingmaschine. Es gelten die folgenden Notationen:
Aus diesen Klassen, lassen sich u. a. folgende Platzkomplexitätsklassen bilden:
Es gibt darüber hinaus noch weitere Platzkomplexitätsklassen, die sich auf exponentiellen oder gar über-exponentiellen Speicherplatzbedarf beziehen.
Als echte Teilmengenbeziehung zwischen Platzkomplexitätsklassen deterministischer Turingmaschinen ist bekannt.
Die Komplexitätsklassen der Zeitkomplexität stehen mit denen der Platzkomplexität in folgender Beziehung:
In der Komplexitätstheorie ist die Platzkomplexität neben der Zeitkomplexität ein wichtiges Maß für die „Schwierigkeit“ (oder eben Komplexität) von Problemen. Die Zeitkomplexität eines Algorithmus kann niemals kleiner sein als dessen Platzkomplexität, da für das Schreiben einer Speicherzelle jeweils ein Rechenschritt benötigt wird.
Formal werden Probleme gemäß ihrer Platzkomplexität oder Zeitkomplexität in Komplexitätsklassen eingeteilt.
This article uses material from the Wikipedia Deutsch article Platzkomplexität, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Abrufstatistik · Autoren Der Inhalt ist verfügbar unter CC BY-SA 4.0, sofern nicht anders angegeben. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Deutsch (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.