Zeitkomplexität

Zeitkomplexität ist ein Begriff aus der theoretischen Informatik und beschreibt, wie sich die Laufzeit eines Algorithmus mit der Größe der Eingabe verhält. Sie wird typischerweise als Funktion der Eingabegröße n ausgedrückt, oft in der sogenannten O-Notation. Diese Notation gibt eine obere Schranke für das Wachstum der Laufzeit an.

Verschiedene Wachstumsraten sind üblich. Eine konstante Zeitkomplexität (O(1)) bedeutet, dass die Laufzeit unabhängig von der Eingabegröße ist. Lineare Zeitkomplexität (O(n)) bedeutet, dass die Laufzeit proportional zur Eingabegröße wächst. Quadratische Zeitkomplexität (O(n^2)) bedeutet, dass die Laufzeit mit dem Quadrat der Eingabegröße wächst. Algorithmen mit logarithmischer Zeitkomplexität (O(log n)) oder linear-logarithmischer Zeitkomplexität (O(n log n)) gelten als sehr effizient, besonders bei großen Eingaben.

Die Analyse der Zeitkomplexität hilft dabei, die Effizienz von Algorithmen zu vergleichen und den am besten geeigneten Algorithmus für ein bestimmtes Problem auszuwählen. Sie ist ein entscheidendes Werkzeug bei der Entwicklung leistungsfähiger Software und Systeme. Bei der Betrachtung der Zeitkomplexität werden meist die schlechtesten Fälle (Worst-Case) analysiert, aber auch Durchschnitts- und Best-Case-Analysen sind relevant.