Big-O-Notation

O-Notation, auch bekannt als Big O Notation, ist eine mathematische Notation, die in der Informatik verwendet wird, um das asymptotische Verhalten von Algorithmen zu beschreiben. Sie repräsentiert die obere Schranke oder das Worst-Case-Szenario der Zeitkomplexität eines Algorithmus in Bezug auf die Eingabegröße. Einfacher ausgedrückt, drückt die O-Notation aus, wie die Laufzeit oder der Speicherbedarf eines Algorithmus relativ zur Eingabegröße wächst.

Hinweis

Das asymptotische Verhalten von Algorithmen bezieht sich darauf, wie sich ihre Leistung ändert, wenn die Größe ihrer Eingabe gegen unendlich geht. Mit anderen Worten, es beschreibt das Verhalten des Algorithmus, wenn die Eingabegröße sehr groß wird.

Häufig verwendete Funktionen in der O-Notation

1. O(1): Konstante Zeit. Die Laufzeit des Algorithmus bleibt unabhängig von der Eingabegröße konstant. Beispiel: Zugriff auf ein Element in einem Array über den Index;

2. O(log n): Logarithmische Zeit. Die Laufzeit wächst logarithmisch mit der Größe der Eingabe. Beispiel: Binäre Suche in einem sortierten Array;

3. O(n): Lineare Zeit. Die Laufzeit wächst linear mit der Größe der Eingabe. Beispiel: Iteration durch alle Elemente in einem Array;

4. O(n log n): Log-lineare Zeit. Die Laufzeit wächst proportional zu n multipliziert mit dem Logarithmus von n. Beispiel: Sortieralgorithmen wie Merge Sort und Quick Sort;

5. O(n^2): Quadratische Zeit. Die Laufzeit wächst quadratisch mit der Größe der Eingabe. Beispiel: Verschachtelte Schleifen, die durch alle Paare von Elementen in einem Array iterieren;

6. O(2^n): Exponentielle Zeit. Die Laufzeit wächst exponentiell mit der Größe der Eingabe. Beispiel: Generierung aller Teilmengen einer Menge;

7. O(n!): Faktorielle Zeit. Die Laufzeit wächst faktoriell mit der Größe der Eingabe. Beispiel: Generierung aller Permutationen einer Sequenz.