DAA - Raumkomplexitäten
In diesem Kapitel werden wir die Komplexität von Rechenproblemen in Bezug auf den Platzbedarf eines Algorithmus diskutieren.
Die räumliche Komplexität teilt viele Merkmale der zeitlichen Komplexität und dient als weitere Möglichkeit, Probleme nach ihren Rechenschwierigkeiten zu klassifizieren.
Was ist Raumkomplexität?
Die Raumkomplexität ist eine Funktion, die die Menge an Speicher (Raum) beschreibt, die ein Algorithmus in Bezug auf die Menge an Eingaben in den Algorithmus benötigt.
Wir sprechen oft davon extra memorybenötigt, ohne den Speicher zu zählen, der zum Speichern der Eingabe selbst benötigt wird. Auch hier verwenden wir natürliche Einheiten (mit fester Länge), um dies zu messen.
Wir können Bytes verwenden, aber es ist einfacher, beispielsweise die Anzahl der verwendeten Ganzzahlen, die Anzahl der Strukturen mit fester Größe usw. zu verwenden.
Am Ende ist die Funktion, die wir entwickeln, unabhängig von der tatsächlichen Anzahl von Bytes, die zur Darstellung der Einheit benötigt werden.
Die Raumkomplexität wird manchmal ignoriert, da der verwendete Raum minimal und / oder offensichtlich ist. Manchmal wird er jedoch genauso wichtig wie die Zeitkomplexität
Definition
Lassen M deterministisch sein Turing machine (TM)das hält an allen Eingängen an. Die Raumkomplexität vonM ist die Funktion $ f \ Doppelpunkt N \ rechter Pfeil N $, wobei f(n) ist die maximale Anzahl von Bandzellen und M scannt alle Längeneingaben M. Wenn die Raumkomplexität vonM ist f(n), Wir können das sagen M läuft im Weltraum f(n).
Wir schätzen die räumliche Komplexität der Turing-Maschine mithilfe der asymptotischen Notation.
Sei $ f \ Doppelpunkt N \ rechter Pfeil R ^ + $ eine Funktion. Die Raumkomplexitätsklassen können wie folgt definiert werden:
SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}
SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}
PSPACE ist die Klasse von Sprachen, die im Polynomraum einer deterministischen Turing-Maschine entscheidbar sind.
Mit anderen Worten, PSPACE = Uk SPACE (nk)
Satz von Savitch
Einer der frühesten Sätze in Bezug auf die Raumkomplexität ist der Satz von Savitch. Nach diesem Theorem kann eine deterministische Maschine nicht deterministische Maschinen mit geringem Platzbedarf simulieren.
Für die zeitliche Komplexität scheint eine solche Simulation einen exponentiellen Zeitanstieg zu erfordern. Für die Raumkomplexität zeigt dieser Satz, dass jede nicht deterministische Turing-Maschine, die verwendetf(n) Raum kann in ein deterministisches TM umgewandelt werden, das verwendet f2(n) Raum.
Der Satz von Savitch besagt daher, dass für jede Funktion $ f \ Doppelpunkt N \ rechter Pfeil R ^ + $ gilt, wobei $ f (n) \ geqslant n $
NSPACE(f(n)) ⊆ SPACE(f(n))
Beziehung zwischen Komplexitätsklassen
Das folgende Diagramm zeigt die Beziehung zwischen verschiedenen Komplexitätsklassen.
Bisher haben wir in diesem Tutorial keine P- und NP-Klassen behandelt. Diese werden später besprochen.