Big-O-Notation: Die Laufzeit von Algorithmen verstehen

Dein Code funktioniert – aber funktioniert er auch noch, wenn aus 100 Datensätzen plötzlich eine Million werden? Genau hier kommt die Big-O-Notation ins Spiel. Sie ist die Sprache, mit der Entwickler beschreiben, wie sich die Laufzeit eines Algorithmus verhält, wenn die Datenmenge wächst. In diesem Beitrag schauen wir uns an, was hinter Begriffen wie O(n) oder O(log n) steckt – mit anschaulichen Python-Beispielen und ohne abschreckende Mathematik.

Warum reicht eine Stoppuhr nicht?

Die naheliegendste Idee, um zwei Lösungen zu vergleichen, ist: Zeit messen. Doch eine Stoppuhr verrät dir nur, wie schnell dein Code auf deinem Rechner mit deinen Testdaten läuft. Auf einem schnelleren Server oder mit zehnmal so vielen Daten sieht das Ergebnis völlig anders aus.

Die Big-O-Notation abstrahiert von solchen Details. Sie fragt nicht „Wie viele Millisekunden?", sondern „Wie stark wächst der Aufwand, wenn die Eingabe wächst?". Damit kannst du Algorithmen vergleichen, ohne sie überhaupt auszuführen – und erkennst Skalierungsprobleme, bevor sie in der Produktion zuschlagen.

Was die Big-O-Notation beschreibt

Big O beschreibt das Wachstumsverhalten im schlimmsten Fall (engl. worst case). Das n steht dabei für die Größe der Eingabe – etwa die Anzahl der Elemente in einer Liste. Konstante Faktoren und kleinere Terme werden bewusst weggelassen, weil sie bei großen Datenmengen kaum noch ins Gewicht fallen.

Ein Beispiel: Ein Algorithmus, der 3 * n + 10 Schritte braucht, wird einfach als O(n) bezeichnet. Uns interessiert die Form der Kurve, nicht die exakte Zahl.

Die wichtigsten Komplexitätsklassen

Diese vier Klassen begegnen dir im Alltag am häufigsten – von sehr gut bis problematisch:

• O(1) – konstant: Der Aufwand bleibt gleich, egal wie groß die Daten sind.
• O(log n) – logarithmisch: Der Aufwand wächst sehr langsam, selbst bei riesigen Datenmengen.
• O(n) – linear: Doppelt so viele Daten bedeuten doppelt so viel Arbeit.
• O(n²) – quadratisch: Zehnmal so viele Daten bedeuten hundertmal so viel Arbeit.

Ein Zugriff auf ein Dictionary ist ein klassisches Beispiel für O(1): Egal, ob es zehn oder zehn Millionen Einträge enthält, der Zugriff dauert gleich lang.

benutzer = {"anna": 29, "ben": 34, "carla": 41}

# Ein einziger Zugriff – unabhängig von der Größe: O(1)
def alter_von(name):
    return benutzer.get(name)

print(alter_von("ben"))  # 34

O(n): Wenn jeder Schritt zählt

Sobald du jedes Element einmal anfassen musst, landest du bei linearer Laufzeit. Das klassische Beispiel ist die Suche in einer unsortierten Liste:

def enthaelt(zahlen, gesucht):
    for zahl in zahlen:        # n Durchläufe im schlimmsten Fall
        if zahl == gesucht:
            return True
    return False

print(enthaelt([4, 8, 15, 16, 23, 42], 16))  # True

Verdoppelst du die Liste, verdoppelt sich im Schnitt auch die Anzahl der Vergleiche. Das ist oft völlig in Ordnung – lineare Algorithmen skalieren vorhersehbar und sind leicht zu verstehen.

Quadratisch wird teuer: O(n²)

Gefährlich wird es, wenn du eine Schleife in eine andere Schleife verschachtelst. Dieser Code prüft, ob eine Liste doppelte Werte enthält:

def hat_duplikate(werte):
    for i in range(len(werte)):
        for j in range(i + 1, len(werte)):
            if werte[i] == werte[j]:
                return True
    return False

Bei 10 Elementen sind das rund 45 Vergleiche, bei 1.000 Elementen schon fast eine halbe Million. Die gute Nachricht: Oft lässt sich O(n²) auf O(n) drücken, indem du ein set als Gedächtnis nutzt:

def hat_duplikate_schnell(werte):
    gesehen = set()
    for wert in werte:        # nur noch n Durchläufe
        if wert in gesehen:
            return True
        gesehen.add(wert)
    return False

Der Trick mit O(log n): die binäre Suche

Wenn deine Daten sortiert sind, kannst du die Suche dramatisch beschleunigen. Die binäre Suche halbiert den Suchbereich mit jedem Schritt:

def binaere_suche(sortiert, ziel):
    low, high = 0, len(sortiert) - 1
    while low <= high:
        mitte = (low + high) // 2
        if sortiert[mitte] == ziel:
            return mitte
        elif sortiert[mitte] < ziel:
            low = mitte + 1
        else:
            high = mitte - 1
    return -1

In einer Liste mit einer Million Einträgen braucht die binäre Suche höchstens etwa 20 Schritte – die lineare Suche dagegen bis zu eine Million. Das ist der ganze Unterschied zwischen O(log n) und O(n).

Big O in der Praxis

Ein paar Faustregeln helfen dir im Alltag:

• Verschachtelte Schleifen über dieselben Daten sind ein Warnsignal für O(n²).
• dict und set bieten in Python durchschnittlich O(1) für Zugriff und Suche – nutze sie für Nachschlage-Aufgaben.
• Optimiere nicht blind: Bei kleinen Datenmengen ist der einfachste Code oft der beste. Big O lohnt sich vor allem dort, wo die Datenmenge spürbar wächst.

Big O sagt übrigens nichts über die absolute Geschwindigkeit aus: Ein O(n)-Algorithmus mit viel Overhead kann bei kleinen Eingaben langsamer sein als ein O(n²)-Algorithmus. Erst wenn die Daten wachsen, gewinnt zuverlässig die bessere Komplexitätsklasse.

Fazit

Die Big-O-Notation ist kein akademischer Selbstzweck, sondern ein praktisches Werkzeug, um die Skalierbarkeit deines Codes einzuschätzen. Wenn du die vier Grundklassen O(1), O(log n), O(n) und O(n²) verinnerlichst, erkennst du teure Stellen oft schon beim Lesen des Codes. Achte auf verschachtelte Schleifen, wähle die richtige Datenstruktur – und denk daran: Der schnellste Algorithmus ist der, den du gar nicht erst ausführen musst.