Big-O-Notation Erklärt mit Code-Beispielen

Ein Zugriff auf ein Python-Dictionary dauert etwa 100 Nanosekunden, egal ob das Dictionary 1.000 oder 1.000.000 Schlüssel enthält. Eine verschachtelte Schleife, die eine Liste auf Duplikate prüft, braucht eine halbe Millisekunde bei 200 Elementen und 136 Millisekunden bei 3.200. Sechzehnmal die Eingabe, fast 280-mal die Wartezeit. Gleiche Maschine, gleiches Python. Die Big-O-Notation ist der Name für diesen Unterschied.

Was die Big-O-Notation misst

Big O beschreibt, wie die Laufzeit (oder der Speicherverbrauch) eines Codestücks wächst, wenn die Eingabe größer wird. Es ist keine Stoppuhr-Messung, und es ist egal, ob Ihr Laptop schnell oder langsam ist. Entscheidend ist die Form der Wachstumskurve: Verdoppelt sich die Zeit, wenn Sie die Eingabe verdoppeln, vervierfacht sie sich, oder bewegt sie sich kaum?

Die Notation lässt alles weg, was diese Form nicht verändert, von konstanten Faktoren bis zur Hardware, auf der der Code läuft. O(n) bedeutet “proportional zu n”, ob die tatsächlichen Kosten nun 3n + 7 oder 0.001n + 1000000 sind. Machen Sie n groß genug, und nur die Form bleibt übrig.

Big-O-Beispiele in Python, zeitgemessen bei wachsenden Eingabegrößen

Jede der folgenden Funktionen wurde mit Pythons timeit-Modul unter Python 3.11 gemessen, bei Eingabegrößen, die eine Größenordnung (oder eine Verdopplung) auseinanderliegen.

Konstante Zeit: ein Dictionary-Zugriff

1
2

def dict_lookup(d, key):
    return d[key]

Die Eingabe wächst um das Tausendfache. Die Zeit pro Aufruf bleibt flach, innerhalb der Messtoleranz. Ein Dictionary ist eine Hash-Tabelle: Python berechnet den Hash des Schlüssels und springt direkt zum passenden Bucket, unabhängig davon, wie viele andere Einträge existieren. Das ist O(1), konstante Zeit.

Lineare Zeit: eine Liste summieren

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Jede Verzehnfachung von n bringt eine etwa zehnfache Zeitzunahme. Die Schleife berührt jedes Element genau einmal, der Aufwand skaliert also direkt mit der Eingabe. Das ist O(n), lineare Zeit, und in dieser Klasse liegt der größte Teil des alltäglichen Codes.

Quadratische Zeit: Duplikate auf die naive Art suchen

1
2
3
4
5
6

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

Eine Verdopplung von n vervierfacht die Zeit bei jedem Schritt ungefähr. Die äußere Schleife läuft n-mal und die innere läuft bei jeder äußeren Iteration fast n-mal, der Gesamtaufwand ist also proportional zu n * n. Das ist O(n^2), quadratische Zeit. Diese Klasse ruiniert produktiven Code, weil sie in einem Test mit 50 Zeilen unauffällig wirkt und bei 50.000 in ein Timeout läuft.

Logarithmische Zeit: binäre Suche

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Eine Tausendfachung von n lässt die Zeit kaum mehr als verdoppeln. Jeder Schleifenschritt verwirft die Hälfte des verbleibenden Bereichs, die nötige Schrittzahl wächst also mit log2(n) statt mit n: etwa 10 Schritte für tausend Elemente, etwa 20 für eine Million. Das ist O(log n). Git bisect führt denselben Algorithmus über die Commit-Historie statt über ein sortiertes Array aus: Es findet den fehlerhaften Commit unter Hunderten in wenigen Schritten, weil jeder Test die Hälfte des verbleibenden Bereichs verwirft.

Linearithmische Zeit: Sortieren

1

sorted_nums = sorted(nums)

Jede Verzehnfachung von n kostet mehr als das Zehnfache an Zeit, aber weit unter dem Hundertfachen, das ein quadratischer Algorithmus zeigen würde. Pythons sorted() nutzt Timsort, das O(n log n) Vergleiche durchführt: Das Mergen läuft in etwa log n Runden ab, und jede Runde berührt jedes der n Elemente einmal, um benachbarte Läufe zu verschmelzen. Jeder General-Purpose-Sortieralgorithmus, den Sie im Alltag verwenden (Timsort, Mergesort, der Durchschnittsfall von Quicksort), landet hier, weshalb O(n log n) als “so gut, wie Sortieren überhaupt werden kann” gilt, statt mit O(n) verglichen zu werden.

Die gängigsten Big-O-Komplexitätsklassen, von schnell nach langsam

Sehen Sie sich die letzten beiden Zeilen an. Der Sprung von O(n log n) zu O(n^2) bei einer Million Elementen ist der Unterschied zwischen einem Report, der in einer Sekunde läuft, und einem, der noch läuft, wenn jemand den Prozess abbricht.

Was die Big-O-Notation verschweigt

Big O beschreibt asymptotisches Wachstum, also das, was passiert, wenn n beliebig groß wird. Drei Dinge fallen durch diese Lücke.

Konstanten sind unsichtbar. Ein O(n) mit einem konstanten Faktor von 1000 kann in der Praxis langsamer sein als ein O(n^2) mit einer winzigen Konstante, für jedes n, das Sie jemals sehen werden. Big O sagt Ihnen, welche Kurve am Ende gewinnt, nicht welche Funktion bei Ihren Daten schneller ist. Deshalb bleibt Insertion Sort, obwohl O(n^2), für sehr kleine Arrays die bessere Wahl. Aus demselben Grund nutzt Timsort einen binären Insertion Sort, um jeden kleinen Lauf (Run) bis zu einer Mindestlänge (Minrun, typischerweise 32-64 Elemente) aufzubauen, bevor es anfängt, Läufe zusammenzuführen.

Ein kleines n zeigt die Kurve nicht. Die quadratischen Zeiten oben wurden erst ab ein paar Hundert Elementen erkennbar quadratisch. Bei n = 10 ist fast alles erledigt, bevor man es bemerkt, weshalb eine Funktion jeden lokal geschriebenen Test besteht und dann bei den Datenmengen in der Produktion versagt.

Speicherkomplexität ist eine eigene Achse. dict_lookup, sum_loop, has_duplicate_naive und binary_search laufen alle mit nahezu konstantem zusätzlichem Speicher: Keine davon reserviert eine zweite, zur Eingabe proportionale Datenstruktur. sorted() tut das sehr wohl: Es gibt eine neue Liste in der Größe der Eingabe zurück, O(n) Speicher, weil es nie in-place sortiert. Manche Algorithmen tauschen Speicher gezielt gegen Geschwindigkeit: Eine memoisierte Fibonacci-Funktion speichert jedes bereits berechnete Ergebnis und gibt O(n) Speicher aus, um O(2^n) Zeit in O(n) zu verwandeln. Wenn Sie die Komplexität einer Funktion angeben, sagen Sie, welche Achse Sie meinen: Die schnellere Variante ist oft die, die mehr Speicher verbraucht.

Wie Sie ein verstecktes O(n^2) in Ihrem Code finden

Die verschachtelte Schleife von vorhin ist der offensichtliche Fall. Der Fall, der es in die Produktion schafft, hat meist keine verschachtelte Schleife in Sicht.

Mitgliedschaftstests in einer Schleife. x in irgendeine_liste ist O(n) bei einer Liste, weil Python sie komplett durchsuchen muss. Diese Prüfung in einer Schleife auszuführen, die bereits n-mal läuft, ergibt O(n^2), ohne dass ein zweites for zu sehen ist:

1
2
3
4
5
6

# O(n^2): "in" durchsucht bei jeder Iteration die ganze Liste
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Tauschen Sie die Liste gegen ein Set, bei dem die Mitgliedschaft O(1) ist, und die Schleife sinkt auf O(n):

1
2
3
4
5
6

# O(n): "in" ist eine Hash-Lookup
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Eine Liste neu aufbauen, statt Elemente anzuhängen. result + [item] reserviert eine neue Liste und kopiert jedes bereits vorhandene Element hinein; result.append(item) lässt die bestehende Liste in-place wachsen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # kopiert jedes Mal alles bisher Gebaute
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) amortisiert
    return result

Eine Liste mit 8.000 Elementen mit + aufzubauen, dauerte 65 ms. Dieselbe Liste mit .append() dauerte 0,15 ms. Der Abstand wächst mit n, weil das eine quadratisch und das andere linear ist.

Die N+1-Abfrage. Sie holen eine Liste von Zeilen und schleifen dann darüber, wobei pro Zeile eine weitere Abfrage für zugehörige Daten abgesetzt wird, sodass aus einer einzigen Abfrage n + 1 werden: O(n) Round-Trips zur Datenbank statt einem einzigen. Ein Index, wie in Wie Datenbankindizes funktionieren beschrieben, verwandelt eine einzelne Suche von einem O(n)-Tabellenscan in O(log n). Für eine Schleife, die tausend einzelne Abfragen absetzt, bringt das nichts. Die Lösung hat dieselbe Form wie die Set-Lösung oben: Ersetzen Sie die Operation pro Zeile durch eine einzige Operation. Hier bedeutet das eine einzige Abfrage mit einem Join, den die SQL-JOIN-Typen erklärt mit Beispielen im Detail durchgeht.

Wie Sie die Komplexität Ihres eigenen Codes messen

Wählen Sie die verdächtige Funktion, meist eine mit einer Schleife, deren Durchlaufzahl von der Datenmenge abhängt. Messen Sie sie mit timeit bei drei oder vier Eingabegrößen, jede davon zehnmal so groß wie die vorherige, und teilen Sie jede Messung durch die vorherige. Ein Verhältnis nahe 1 ist O(1) oder O(log n). Nahe 10 ist linear. Zwischen 10 und 100 ist O(n log n), wie die 17-21 in der sorted()-Tabelle zeigen. Nahe 100 bedeutet, Sie haben ein O(n^2) aufzuspüren; wenn das die großen Größen zu langsam macht, um darauf zu warten, verdoppeln Sie n statt es zu verzehnfachen, und suchen Sie nach einem Verhältnis nahe 4. Fangen Sie mit den Mitgliedschaftstests auf Listen und den +-Neuaufbauten in dieser Schleife an, dann mit jeder Abfrage, die einmal pro Zeile abgesetzt wird.

Verwandte Artikel

• Git Bisect: den Commit finden, der einen Bug eingeführt hat
• Wie Datenbankindizes Funktionieren und Wann Sie Nutzen
• SQL-JOIN-Typen Erklärt mit Beispielen