Das Kefk Network Wiki befindet sich im Testbetrieb.
Komplexitätsklasse
Aus Kefk.
Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen bzw. Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Sie ist definiert durch das asymptotische Verhalten der Obergrenze (oder des Mittelwertes oder der Untergrenze) des Ressourcenbedarfs (insbesondere an Laufzeit und Speicherplatz) in Abhängigkeit von einer Problemgröße n (Länge der Eingabe).
Wenn allgemein von Komplexität die Rede ist, ist meistens 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 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 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, aber auch ein Algorithmus existiert, der P in f(n) Schritten löst. Ein Problem A, das mit geringem Aufwand auf ein Problem B zurückgeführt 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.
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
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Komplexit%C3%A4tsklasse, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
