Zeitkomplexität

Die Zeitkomplexität eines Algorithmus beschreibt, wie sich die Laufzeit in Abhängigkeit von der Eingabegröße verhält.

Zur Analyse wird oft die Big-O-Notation verwendet.

Die O-Notation (auch Big-O-Notation genannt) wird verwendet, um die Laufzeit eines Algorithmus in Bezug auf die Größe der Eingabe zu beschreiben. Sie gibt an, wie die Laufzeit wächst, wenn die Eingabedaten (n) immer größer werden.

Was ist n?

n bezeichnet die Eingabegröße eines Algorithmus. Zum Beispiel kann es sich um die Anzahl der Elemente in einem Array handeln, das durch einen Algorithmus verarbeitet wird. Wenn ein Algorithmus also ein Array mit 1000 Elementen durchläuft, dann ist n gleich 1000.

Was sind "Operationen"?

Mit "Operationen" sind die grundlegenden Berechnungen oder Schritte gemeint, die der Algorithmus während seiner Ausführung durchführt. Dies könnte beispielsweise das Vergleichen von zwei Zahlen, das Austauschen von Elementen in einem Array oder das Berechnen einer Zahl sein. Die Anzahl der durchgeführten Operationen gibt Aufschluss darüber, wie effizient der Algorithmus ist.

Wie funktioniert die O-Notation?

Die O-Notation beschreibt das Wachstum der Anzahl der Operationen in Bezug auf die Eingabegröße. Sie berücksichtigt dabei den schlimmsten Fall (Worst-Case-Szenario). Zum Beispiel bedeutet O(n), dass die Anzahl der Operationen mit der Größe der Eingabe direkt wächst. Wenn die Eingabegröße doppelt so groß wird, verdoppelt sich auch die Anzahl der Operationen.

O-Notation	Erklärung	Beispiel
O(1)	Konstante Zeit. Die Anzahl der Operationen bleibt gleich, egal wie groß die Eingabe ist.	Zugriff auf ein Element in einem Array (z. B. array[i]).
O(log n)	Logarithmische Zeit. Die Anzahl der Operationen wächst langsam, da die Eingabe bei jeder Iteration halbiert wird.	Binäre Suche in einem sortierten Array.
O(n)	Lineare Zeit. Die Anzahl der Operationen wächst proportional zur Eingabegröße.	Durchlaufen eines Arrays mit n Elementen.
O(n log n)	Quasilineare Zeit. Eine Kombination aus linearer und logarithmischer Zeit.	Merge Sort oder Quicksort.
O(n²)	Quadratische Zeit. Die Anzahl der Operationen wächst mit dem Quadrat der Eingabegröße.	Bubble Sort oder Insertion Sort.
O(2ⁿ)	Exponentialzeit. Die Anzahl der Operationen wächst extrem schnell mit der Eingabegröße.	Naive Berechnung von Fibonacci-Zahlen.
O(n!)	Fakultative Zeit. Die Anzahl der Operationen wächst mit der Fakultät der Eingabegröße.	Brute-Force-Lösung für das Traveling Salesman Problem.