O-Notation und Komplexität

Wenn ein Algorithmus auf einem kleinen Eingabearray funktioniert, heißt das nicht, dass er auch für 10 Millionen Elemente brauchbar ist. Die Komplexitätsanalyse beschreibt, wie der Aufwand eines Algorithmus mit der Eingabegröße \( n \) wächst. Sie abstrahiert von Hardware und Programmiersprache und erlaubt fundierte Vergleiche zwischen Algorithmen.

Eine Funktion \( f(n) \) liegt in \( \mathcal{O}(g(n)) \), wenn es Konstanten \( c > 0 \) und \( n_0 > 0 \) gibt, sodass

\[ f(n) \leq c \cdot g(n) \quad \text{für alle } n \geq n_0 . \]

Die O-Notation gibt damit eine obere Schranke des asymptotischen Wachstums an. Konstante Faktoren und kleinere Terme werden ignoriert: \( 5n^2 + 3n + 7 \in \mathcal{O}(n^2) \).

• \( \mathcal{O}(1) \) – konstant. Beispiel: Zugriff auf a[5] oder HashMap.get.
• \( \mathcal{O}(\log n) \) – logarithmisch. Beispiel: binäre Suche.
• \( \mathcal{O}(n) \) – linear. Beispiel: lineare Suche, Summe aller Elemente.
• \( \mathcal{O}(n \log n) \) – linearithmisch. Beispiel: MergeSort, HeapSort.
• \( \mathcal{O}(n^2) \) – quadratisch. Beispiel: BubbleSort, SelectionSort.
• \( \mathcal{O}(n^3) \) – kubisch. Beispiel: Matrizenmultiplikation (klassisch).
• \( \mathcal{O}(2^n) \) – exponentiell. Beispiel: naive Fibonacci, Türme von Hanoi.
• \( \mathcal{O}(n!) \) – faktoriell. Beispiel: Brute-Force Travelling Salesman.

Für \( n = 1\,000\,000 \) ergibt sich:

O(1)        ≈       1
O(log n)    ≈      20
O(n)        ≈  10^6
O(n log n)  ≈  2*10^7
O(n^2)      ≈  10^12
O(2^n)      ≈  unberechenbar

Daran sieht man: schon ein quadratischer Algorithmus ist für eine Million Elemente nicht mehr praktisch durchführbar.

for (int i = 0; i < n; i++) {           // n Schritte
    for (int j = 0; j < n; j++) {       // n Schritte
        sum += a[i] * a[j];              // konstant
    }
}

Innere Operation: konstant. Innere Schleife: \( n \). Äußere Schleife: \( n \). Gesamt: \( n \cdot n = n^2 \), also \( \mathcal{O}(n^2) \).

Die Komplexität kann je nach Eingabe variieren. Bei BubbleSort ist der Best Case \( \mathcal{O}(n) \) (bereits sortiert), der Worst Case \( \mathcal{O}(n^2) \) (umgekehrt sortiert) und der Average Case ebenfalls \( \mathcal{O}(n^2) \). In der Praxis ist meist der Worst Case relevant.

Konstanten werden mitgeschleppt (O(2n) statt O(n)), kleinere Summanden bleiben stehen, der Algorithmus wird in der falschen Klasse eingeordnet (z. B. wird MergeSort als \( \mathcal{O}(n^2) \) bezeichnet), die Mitberechnung des Speicherbedarfs wird vergessen.

Zusammenfassung: Die O-Notation beschreibt das asymptotische Wachstum von Laufzeit oder Speicher. Wichtige Klassen: \( \mathcal{O}(1) \), \( \mathcal{O}(\log n) \), \( \mathcal{O}(n) \), \( \mathcal{O}(n \log n) \), \( \mathcal{O}(n^2) \), \( \mathcal{O}(2^n) \).

Abitur-Tipp: Begründe Komplexitätsangaben immer durch Zählen der inneren Schleifeniterationen und des Rekursionsbaums.