Komplexitätsklasse
Wenn allgemein von Komplexität die Rede ist, ist meist das Verhalten der Obergrenze der Zeitdauer einer Berechnung gemeint (worst case der asymptotische Laufzeit, Zeitkomplexität).
Die Schwierigkeit bei der Bestimmung einer Komplexitätsklasse eines Problems liegt darin, dass man alle möglichen Algorithmen für ein Problem betrachten müsste, um die Komplexität des Problems zu bestimmen. Man muss also beweisen, dass ein bestimmter Algorithmus optimal für dieses Problem ist. Die Komplexität wird häufig mit Hilfe der Landau-Symbole beschrieben, um von Eigenheiten bestimmter Implementierungen zu abstrahieren.
Die Komplexitätsklasse eines Algorithmus ist nur in einer konkreten Implementation auf einer Maschine, z.B. auf einer Turingmaschine oder im Lambda-Kalkül feststellbar. Die Komplexitätsklassen der Implementationen eines Algorithmus auf unterschiedlichen Maschinenmodellen sind jedoch meist ähnlich oder sogar -- je nach Abstraktionslevel -- gleich.
Es wird festgestellt, dass nur bestimmte Klassen dieser Größe sinnvoll unterscheidbar sind, die alle mit einer charakteristischen Gleichung beschrieben werden. So interessieren z.B. konstante Faktorenen in der Komplexität eines Algorithmus nicht - schließlich gibt es in der Realität (Computer) auch Maschinen, deren Ausführungsgeschwindigkeit sich um einen konstanten Faktor unterscheidet. Hier wird auch klar, warum keine Einheiten gebraucht werden und wie die Landau-Notation zu verstehen ist.
Eine wichtige Rolle bei der Einteilung der Komplexitätsklassen spielt die Unterscheidung von Zeitkomplexität und Platzkomplexität, bei deren Betrachtung Zeit bzw. Platz beschränkt werden. Weiterhin unterscheidet man deterministische Maschinen von nichtdeterministischen. Informell lässt sich sagen, dass Platz mächtiger ist als Zeit und Nichtdeterminismus meist mächtiger als Determinismus, allerdings jeweils nur exponentiell mächtiger. Genauere Abschätzungen hierzu geben der Satz von Savitch und der Satz von Immermann/Szelepcsényi.
Komplexitätsklassen werden häufig auf Probleme bezogen. So bedeutet eine Komplexität des Problems P von f(n) (bei Eingabelänge n), dass jeder Algorithmus der P löst, mindestens eine Rechenzeit von f(n) benötigt, es aber auch ein Algorithmus existiert, welcher P in f(n) Schritten löst. Ein Problem A, welches mit geringem Aufwand auf ein Problem B zurückgeführt werden kann, gehört mindestens zur Komplexitätsklasse von B. B wird dann härter als A genannt. Ein Problem A ist k-hart, wenn sich alle anderen Probleme der Klasse k auf A zurückführen lassen. Liegt ein k-hartes Problem A selbst in der Klasse k, wird es k-vollständig genannt.
Beispiel
Rasenmähen hat mindestens lineare Komplexität (in der Fläche), denn man muss die gesamte Fläche mindestens einmal überfahren. Suchen im Telefonbuch hat hingegen nur logarithmische Komplexität, denn bei doppelt so dickem Telefonbuch schlägt man dieses nur einmal öfter auf (z.B. genau in der Mitte - dann hat man das Problem auf die Hälfte reduziert -- siehe binäre Suche).Zusammenhänge
Siehe auch
