ZeitkomplexitätAlgorithmen

Zeitkomplexität bezeichnet die Wachstumsrate der Laufzeit eines Algorithmus in Abhängigkeit von der Eingabegröße n. Sie wird üblicherweise durch asymptotische Notationen wie Big-O (O), Big-Theta (Θ) und Big-Omega (Ω) beschrieben. Big-O gibt eine obere Schranke an, Θ eine enge, mittlere Wachstumsrate, und Ω eine untere Schranke. Zeitkomplexität ist eine theoretische Abschätzung, die konstante Faktoren und Maschinenparameter ausklammert.

Man unterscheidet Best-Case, Worst-Case und Average-Case. Der Best-Case beschreibt die günstigste Eingabeform, der Worst-Case die ungünstigste, und der Average-Case den erwarteten Verlauf über alle Eingaben.

Typische Beispiele: Das Durchlaufen einer Liste zur Suche hat O(n). Eine Suche in einer sortierten Liste mittels Binärsuche hat O(log n). Sortieralgorithmen wie Quicksort haben durchschnittlich O(n log n) Laufzeit, im schlechtesten Fall O(n^2); Merge-Sort garantiert O(n log n). Exponentielle oder noch schneller wachsende Raten wie O(2^n) oder O(n!) treten häufig bei bestimmten rekursiven oder bruteforce-Ansätzen auf.

Zur Bestimmung analysiert man die Anzahl der grundlegenden Operationen in Abhängigkeit von n oder löst entsprechende Rekursionsgleichungen. Praktisch beeinflussen auch Faktoren wie Cacheverhalten, Parallelisierung und Hardware die tatsächliche Laufzeit, weshalb Zeitkomplexität als theoretische Orientierung dient, nicht als exakte Messgröße.