Big-O-Notation

Kurz: Die Big-O-Notation beschreibt, wie stark der Zeit- oder Speicherbedarf eines Algorithmus mit der Eingabegröße n wächst – ohne Rücksicht auf Konstanten und konkrete Hardware.

Genauer: Sie erlaubt, Algorithmen unabhängig vom Rechner zu vergleichen: O(n) heißt, die Laufzeit wächst proportional zur Eingabe; O(n²) heißt, bei doppelter Eingabe vervierfacht sie sich. Maßgeblich ist der am stärksten wachsende Term im schlechtesten Fall (oder im Durchschnitt).

Im Detail

Klasse	Name	Beispiel
O(1)	konstant	Array-Zugriff, Hashmap-Suche
O(log n)	logarithmisch	Binäre Suche, ausgeglichener Suchbaum
O(n)	linear	Liste durchlaufen
O(n log n)	linearithmisch	Mergesort, Quicksort (Durchschnitt)
O(n²)	quadratisch	Bubblesort, verschachtelte Schleifen
O(2ⁿ)	exponentiell	naives Fibonacci, alle Teilmengen
O(n!)	faktoriell	alle Permutationen

Bei n = 1 000 000 braucht O(n) etwa eine Million Schritte, O(n log n) rund 20 Millionen, O(n²) aber eine Billion – das ist der Unterschied zwischen Sekunden und Tagen.

def enthaelt(liste, x):          # O(n): im schlechtesten Fall alle Elemente prüfen
    for e in liste:
        if e == x:
            return True
    return False
 
def hat_duplikate(liste):        # O(n): Menge benutzt Hashing
    gesehen = set()
    for e in liste:
        if e in gesehen:
            return True
        gesehen.add(e)
    return False
 
def hat_duplikate_langsam(liste):   # O(n²): jedes Paar vergleichen
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                return True
    return False

Regeln zum Abschätzen

• Konstanten und Terme niedrigerer Ordnung fallen weg: 3n² + 5n + 7 → O(n²).
• Aufeinanderfolgende Schritte addieren sich, verschachtelte Schleifen multiplizieren sich.
• Halbieren der Eingabe pro Schritt führt zu O(log n).
• Es gibt auch Speicher-Komplexität: Wie viel zusätzlicher Speicher wird gebraucht?

Big-O ist ein Werkzeug zum Vergleichen, kein Messergebnis: Für kleine n kann ein O(n²)-Verfahren schneller sein als ein O(n log n)-Verfahren mit hohem Aufwand. Gemessen wird mit einem Profiler.

Siehe auch: Algorithmen, Sortieren, Datenstrukturen, Rekursion