Komplexität (Informatik)

Die algorithmische Komplexität eines Problems, ist die "Geschwindigkeit" die ein optimaler Algorithmus für dieses Problem mindestens braucht oder brauchen müsste. Die Schwierigkeit liegt darin, dass man somit alle Algorithmen für ein Problem betrachten müsste, um die Komplexität des selben zu bestimmen. 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.

Beispiel: Rasenmähen hat lineare Komplexität, denn bei doppelter Rasenfläche braucht man auch doppelt so lange. 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).

Es kommt auch vor, dass nicht das Zeitverhalten des Algorithmus betrachtet wird, sondern z.B. der Speicherbedarf oder irgend ein anderer Bedarf an Ressourcen.

Zur mathematischen Formulierung der Komplexität bedient man sich des Landau-Symbols O. Es steht z.B. O(N) für lineare Komplexität, O(N²) für quadratische usw.

Genaueres findet man in der Komplexitätstheorie.