UniProMax/Algorithmen/big-o-notation

Big-O Notation

Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?

3Lerneinheiten

Relevant für:Informatik(Klausurniveau)Wirtschaftsinformatik(Grundlagen)Data Science(Grundlagen)

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Big-O Notation

Big-O beschreibt, wie sich die Laufzeit oder der Speicherbedarf eines Algorithmus verhält, wenn die Eingabe-Größe wächst.

Statt Mikro-Optimierungen interessiert uns: Wie skaliert dein Code? Funktioniert er noch bei 1.000 Elementen? Bei 1.000.000?

Die Idee in einem Satz

Big-O ignoriert konstante Faktoren und schaut nur auf die dominante Wachstumsrate für sehr große Eingaben.

Beispiel: Eine Funktion, die $3n^2 + 50n + 1000$ Operationen braucht, ist O(n²). Bei großem $n$ dominiert das $n^2$ , alles andere ist Rauschen.

Die wichtigsten Klassen

Big-O	Name	Verhalten
O(1)	konstant	Egal wie groß n: gleiche Zeit
O(log n)	logarithmisch	Verdoppelung von n addiert nur eine Operation
O(n)	linear	Doppelte Eingabe = doppelte Zeit
O(n log n)	linearithmisch	Linear plus ein bisschen mehr
O(n²)	quadratisch	Doppelte Eingabe = vierfache Zeit
O(2ⁿ)	exponentiell	Jedes zusätzliche Element verdoppelt die Zeit

Konkrete Beispiele

O(1) — Array-Zugriff per Index:

java// snippet

int wert = arr[5];

Index-Zugriff in Java: konstante Zeit, egal wie groß das Array ist.

Egal ob das Array 10 oder 10 Millionen Einträge hat: der Zugriff ist immer gleich schnell.

O(n) — Linear durch ein Array suchen:

java// snippet

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
}
return -1;

Im schlimmsten Fall musst du jedes Element prüfen.

Im schlimmsten Fall (Element nicht vorhanden) wirst du jedes Element einmal anfassen.

O(n²) — Verschachtelte Schleife:

java// snippet

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // ... etwas tun
    }
}

Bei n = 100: 10.000 Iterationen. Bei n = 1000: 1.000.000.

Bei $n = 100$ sind das 10.000 Operationen. Bei $n = 1000$ sind es 1.000.000: Faktor 100 mehr Eingabe gibt Faktor 10.000 mehr Arbeit.

Warum das wichtig ist

Eine Bubblesort-Implementierung braucht O(n²) Zeit. Mergesort braucht O(n log n).

Bei 1.000 Einträgen:

Bubblesort: ~1.000.000 Operationen
Mergesort: ~10.000 Operationen

Das ist Faktor 100 schneller: durch die richtige Algorithmuswahl, nicht durch besseren Code.

Was Big-O NICHT sagt

Big-O ist eine Worst-Case-Abschätzung für sehr große $n$ . Bei kleinen Eingaben kann eine theoretisch schlechtere Komplexität schneller sein, weil sie weniger Overhead hat.

Beispiel: Für $n < 50$ ist eine simple Insertion-Sort oft schneller als Mergesort, obwohl Insertion-Sort O(n²) und Mergesort O(n log n) ist. Java's Arrays.sort() und Python's sorted() nutzen deshalb Timsort, das bei kleinen Subarrays auf Insertion-Sort wechselt.

Merksatz: Big-O sagt dir was passiert wenn n gross wird, nicht was bei einer konkreten Eingabe wirklich am schnellsten ist.

KategorieAlgorithmen Baut darauf aufBubblesort