Komplexitätsklasse

Die Komplexität wird häufig mit Hilfe der Landau-Symbole beschrieben, um von Eigenheiten bestimmter Implementierungen und Berechnungsmodelle zu abstrahieren. Die Schwierigkeit bei der Bestimmung der genauen Komplexität eines Problems liegt darin, dass man hierfür sämtliche mögliche Algorithmen betrachten müsste. Man muss also beweisen, dass ein bestimmter Algorithmus optimal für dieses Problem ist.

Die Komplexitätsklasse eines Algorithmus ist nur in einer konkreten Implementierung 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 meistens ä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 Faktoren 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 meistens mächtiger als Determinismus, allerdings jeweils nur exponentiell mächtiger. Genauere Abschätzungen hierzu geben der Satz von Savitch und der Satz von Immerman und Szelepcsényi.

Ein Problem A, das mit geringem Aufwand auf ein Problem B zurückgeführt (reduziert) werden kann, gehört mindestens zur Komplexitätsklasse von B. B wird dann schwerer als A genannt. Ein Problem A ist K-schwer, wenn sich alle anderen Probleme der Klasse K auf A zurückführen lassen. Liegt ein K-schweres Problem A selbst in der Klasse K, wird es K-vollständig genannt.^[1]

• Rasenmähen hat mindestens lineare Komplexität (in der Fläche), denn man muss die gesamte Fläche mindestens einmal überfahren. Das heißt, der Zeitaufwand um ${\displaystyle n}$  m² Rasen zu mähen ist (${\displaystyle n}$  * Konstante) Sekunden. Für einen 3 Mal so großen Rasen braucht man 3 Mal so lange zum Mähen – der Zeitaufwand wächst linear.
• Einfache („dumme“) Sortierverfahren haben häufig eine quadratische Zeitkomplexität: braucht man für ${\displaystyle n=20}$  Bücher z. B. 15 Sekunden, um sie zu sortieren, so bräuchte man (mit diesem einfachen Verfahren) für 10 Mal so viele Bücher 100 Mal so lange, und für 50 Mal so viele Bücher dann 2500 Mal so viel Zeit – der Zeitaufwand steigt quadratisch.
• Suchen im Telefonbuch hat hingegen nur logarithmische Komplexität bei einer binären Suche, wenn man den jeweils verbliebenen Suchbereich immer in der Mitte aufschlägt, ob man zu weit vor oder hinter dem gesuchten Namen liegt.
  Bei einem doppelt so dicken Telefonbuch schlägt man dieses nur ein Mal öfter auf, denn das halbiert den Suchbereich wieder auf das vorige Problem. Der Zeitaufwand, in ${\displaystyle n}$  Einträgen zu suchen, wächst dann mit ${\displaystyle \log _{2}(n)}$ . In doppelt so vielen Telefonnummern zu suchen, braucht nicht doppelt so viele Suchschritte, sondern nur genau einen zusätzlichen.

• Liste von Komplexitätsklassen
• Komplexitätstheorie

1. ↑ Natalia Kliewer: Komplexitätstheorie. In: Lexikon der Wirtschaftsinformatik, Online-Lexikon, Oldenbourg Wissenschaftsverlag.