Platzkomplexität - LinkFang.de





Platzkomplexität


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.

Notation

Die Platzkomplexität wird immer in Bezug auf ein Maschinenmodell angegeben. In der Regel ist das Bezugsmodell die Turingmaschine. Es gelten die folgenden Notationen:

  • Mit [math]\text{DSPACE}(f)[/math] werden alle Probleme bezeichnet, die von einer deterministischen Turingmaschine entschieden werden können, die bei einer Eingabe der Länge [math]n[/math] höchstens [math]f(n)[/math] Speicherzellen für die Berechnung benutzt hat.
  • Mit [math]\text{NSPACE}(f)[/math] werden alle Probleme bezeichnet, die von einer nicht-deterministischen Turingmaschine entschieden werden können, die bei einer Eingabe der Länge [math]n[/math] höchstens [math]f(n)[/math] Speicherzellen für die Berechnung benutzt hat.

Aus diesen Klassen, lassen sich u. a. folgende Platzkomplexitätsklassen bilden:

  • [math]\text{L} := \bigcup_{f \in O(\log(n))}{\text{DSPACE}(f)}[/math]
  • [math]\text{NL} := \bigcup_{f \in O(\log(n))}{\text{NSPACE}(f)}[/math]
  • [math]\text{PSPACE} := \bigcup_{f \in O(n^k), k \in \mathbb{N}}{\text{DSPACE}(f)}[/math]
  • [math]\text{NPSPACE} := \bigcup_{f \in O(n^k), k \in \mathbb{N}}{\text{NSPACE}(f)}[/math]

Es gibt darüber hinaus noch weitere Platzkomplexitätsklassen, die sich auf exponentiellen oder gar über-exponentiellen Speicherplatz beziehen.

Beziehungen

Als echte Teilmengenbeziehung zwischen Platzkomplexitätsklassen deterministischer Turingmaschinen ist [math]\text{L}\subsetneq\text{PSPACE}[/math] bekannt.

Die Komplexitätsklassen der Zeitkomplexität stehen mit denen der Platzkomplexität in folgender Beziehung:

[math]\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} = \text{NPSPACE}[/math]

Sonstiges

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.

Siehe auch


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Platzkomplexität (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.