Laufzeitkomplexität

Laufzeitkomplexität beschreibt, wie sich die Laufzeit eines Algorithmus mit zunehmender Eingabegröße n verändert. Sie wird verwendet, um das Verhalten eines Algorithmus unabhängig von konkreten Maschinenparametern abzuschätzen und zu vergleichen. Die gängigste Darstellung erfolgt durch die Big-O-Notation, die eine obere Grenze des Wachstums angibt.

Neben Big-O werden Omega-Notation (untere Grenze) und Theta-Notation (genaues Wachstum) verwendet. Die Zeitkomplexität bezieht sich auf die Anzahl der Grundoperationen, die der Algorithmus in Abhängigkeit von n ausführt, wobei Konstanten und niedrigere-Ordnungsterme häufig vernachlässigt werden.

Typische Beispiele: O(1) bedeutet konstante Zeit, unabhängig von n. O(log n) trifft zu, wenn jede Schwelle die Eingabe um einen Faktor teilt, wie bei binärer Suche. O(n) steht für lineare Zeit, bei der alle Elemente einer Eingabe einst durchlaufen werden. O(n log n) tritt bei vielen effizienten Sortieralgorithmen auf. O(n^2) ergibt sich aus verschachtelten Schleifen über n Elemente. O(2^n) und O(n!) kennzeichnen exponentielles bzw. faktorielles Wachstum und treten bei einigen Brute-Force-Lösungen auf.

Best-Case, Worst-Case und Average-Case geben verschiedene Szenarien an: Worst-Case berücksichtigt den ungünstigsten Verlauf, Best-Case den günstigsten, und Average-Case versucht, eine mittlere Erwartung abzuschätzen. In der Praxis wird oft die Worst-Case-Analyse verwendet, um Worst-Transparenz und Worst-Performance sicher abzudecken.

Anwendung: Die Analyse der Laufzeitkomplexität hilft bei der Auswahl geeigneter Algorithmen und Datenstrukturen, beim Abschätzen von Skalierungsproblemen und beim Treffen von Designentscheidungen auf Basis der erwarteten Eingabegrößen. Faktoren wie Implementierung, Compiler, Hardware und Cache-Verhalten können die tatsächliche Laufzeit beeinflussen, ändern jedoch nichts an der zugrunde liegenden Wachstumsordnung.