Die Komplexitätsklasse ist definiert durch das asymptotische Verhalten der Obergrenze/des Mittelwertes/der Untergrenze der Zeitdauer/des Speicherbedarfs einer Berechnung in Abhängigkeit von einer Problemgröße
n. Die Laufzeit kann mit Hilfe der Landau-Symbole beschrieben werden.
Wenn allgemein von Komplexität die Rede ist, ist meist das Verhalten der Obergrenze der Zeitdauer einer Berechnung gemeint.
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 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.
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 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.
Dieser Beitrag ist aus der XML-Version der deutschen WikiPedia® entwickelt worden und unterliegt inhaltlich den GNU FDL-Lizenzbestimmungen. Linkziele außerhalb der wikipedia-Inhalte unterliegen den Urheberrechten der jeweiligen Anbieter
( DirectDownloads ) Kalenderblätter druckfertig aufbereitet für Schmuckblätter zum Selbstdrucken im Word DOC6/RTF Format, je Euro 5 über Click&BuyJAN | FEB | MÄRZ APRIL | MAI | JUNI JULI | AUG | SEPT OKT | NOV | DEZ
Das Geschenk für jeden Anlass, nicht nur bei 'runden' Jubiläen Andere Einzeltage oder Zahlungsarten bitte HIER bestellen
Diese Web Site verdient ihr Geld durch Produktverkäufe (CD-ROM, downloads) und in erster Linie durch Anzeigen. Wenn Sie als Webmaster zuverlässige Partner suchen für Ihr eigenes Anzeigenschäft, dürfen Sie sich gerne auf unsere Empfehlungen stützen:
z.B.: GigaCash & ProfiWin
