Kleines Nachschlagewerk Informatik
Komplexität
Worum geht es?
Hierbei geht es darum, wie sich die Rechenzeit bzw. der Speicherverbrauch von Algorithmen entwickelt, wenn man die Datenmenge erhöht. Führt eine Verdopplung der Daten auch zu einer Verdopplung der Rechenzeit?

Hierbei geht es nicht darum, wie lange ein Durchlauf auf einer bestimmten Maschine dauert oder wie viel Byte an Speicher man benötigt. Es geht nur um den funktionalen Zusammenhang zwischen Datenmenge und Rechenzeit bzw. Speicherplatz.

Dies ist notwendig, um Algorithmen zu vergleichen bzw. Aussagen über ihre sinnvolle Anwendung bei großen Datenmengen zu treffen
Ein Beispiel
Es gibt Probleme, die sich nur durch Ausprobieren lösen lassen, z.B. durch Kombination aller Möglichkeiten. Kommt nur eine neue Möglichkeit hinzu, verdoppelt sich die Rechenzeit. Ein Programmierer hat mit einigen Testdaten (z.B. mit 100 Datensätzen) ein Programm erfolgreich getestet. Rechenzeit fiel ihm nicht auf, vielleicht waren es 10 Millisekunden. Der Kunde arbeitet üblicherweise mit einigen tausend Datensätzen.

100 Datensätze waren 10 Millisekunden, dann sind 101 Datensätze - exponentielles Wachstum wie beim Probieren vorausgesetzt - in 20 Millisekunden bearbeitet, 102 in 40 Millisekunden. Bis zur 200 muss man noch 98 Mal verdoppeln. 1,26 * 10^28s. Das Alter des Universums beträgt etwa 5 * 10^17s.
Komplexitätsklassen
Zur Unterscheidung teilt man die Algorithmen in Klassen ein. Die Klasse richtet sich nach dem funktionalen Zusammenhang: Rechenzeit = f(Datenmenge) bzw. Speicherplatz = f(Datenmenge).
Die O-Notation
Zur Bezeichnung hat sich die O-Notation durchgesetzt:

O(1)konstant
O(n)linearer Zusammenhang
O(n^2)quadratischer Zusammenhang
O(n^3)kubischer Zusammenhang
O(log n)logarithmischer Zusammenhang
O(n log n)linear-logarithmischer Zusammenhang, kurz n-log-n
O(2^n)exponentielle Zusammenhang