Algorithmuskomplexität

Die Algorithmuskomplexität ist ein Maß dafür, wie der Ressourcenbedarf eines Algorithmus mit wachsender Eingabegröße n wächst. Typische Ressourcen sind Zeit und Speicher (Raum). Die Zeitkomplexität beschreibt die Anzahl der Grundoperationen, die ein Algorithmus in Abhängigkeit von n benötigt. Häufige Notationen sind Big-O, Theta und Omega, die Ober- bzw. Untergrenze für das Wachstum festhalten. Im praktischen Kontext spricht man oft vom Worst-case, Best-case und Average-case.

Beispiele verdeutlichen das Spektrum: Ein linearer Algorithmus hat O(n), eine Binärsuche in sortierten Daten O(log n), und ein effizienter Sortieralgorithmus wie Mergesort O(n log n). Quadratische Algorithmen wie Bubblesort haben O(n^2). Die Raumkomplexität beschreibt den zusätzlichen Speicher, der über den Eingaberaum hinaus benötigt wird.

Bei der Analyse wird häufig das RAM-Modell verwendet, in dem grundlegende Operationen in konstanter Zeit erfolgen. Die asymptotische Komplexität betrachtet das Verhalten für große n und vernachlässigt Konstantenfaktoren. Dennoch beeinflussen Implementierung, verwendete Datenstrukturen, Programmiersprache, Compiler-Optimierungen und Hardware die reale Laufzeit.

Die Komplexitätsanalyse dient der Einschätzung der Skalierbarkeit von Algorithmen, der Auswahl geeigneter Algorithmen und der Identifizierung von Engpässen. Sie ersetzt nicht das empirische Profiling, ergänzt es aber durch eine theoretische Einschätzung.