Algorithmen, die rechtzeitig fertig werden: Ein Komplexitäts-Realitätscheck

Du schreibst eine Funktion, testest sie mit deinen Testdaten, und sie funktioniert einwandfrei. Dann geht sie in Produktion – 500.000 Zeilen statt 500 – und die Anfrage läuft ab. Das passiert ständig, und es ist fast immer ein Komplexitätsproblem, das sich hinter Code verbirgt, der im kleinen Maßstab vernünftig aussah.

Warum dein Laptop dich belogen hat

Ein O(n²) Algorithmus, der auf 100 Elemente läuft, macht 10.000 Operationen. Das ist auf jeder Maschine sofort erledigt. Führe denselben Algorithmus auf 100.000 Elementen aus und du landest bei 10 Milliarden Operationen – Minuten oder Stunden statt Millisekunden. Der Sprung von n zu n² fühlt sich nicht gefährlich an, bis n groß wird. Genau deshalb rutscht es durch Code Review und lokale Tests.

Ein klassisches Beispiel: Duplikate mit einer verschachtelten Schleife prüfen.

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

Das ist O(n²). Tausch es gegen ein Set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Jetzt ist es O(n). Set-Lookups sind durchschnittlich O(1), also skaliert die ganze Funktion linear statt quadratisch. Bei 10.000 Elementen ist das der Unterschied zwischen etwa 100 Millionen Vergleichen und 10.000.

Messe, bevor du optimierst

Rat nicht. Nutze timeit für Mikro-Benchmarks:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Für größere Funktionen profiliere mit cProfile:

python -m cProfile -s cumulative myscript.py

Schau auf die cumtime Spalte. Wenn eine Funktion 90% der Runtime frisst, das ist dein Ziel. Code zu optimieren, der kein Engpass ist, verschwendet deine Zeit und fügt Komplexität ohne Gewinn hinzu.

Häufige Muster, die leise langsam werden

Wiederholte Listenmitgliedschaftsprüfungen. if x in my_list ist O(n) für eine Liste, aber durchschnittlich O(1) für ein Set oder Dict. Wenn du Mitgliedschaft inmitten einer Schleife prüfst, gibt dir diese O(n) Prüfung in einer O(n) Schleife insgesamt O(n²). Tausch die Liste gegen ein Set und du bist zurück zu O(n).

String-Verkettung in einer Schleife. In Python ist result += chunk in einer Schleife über Strings im schlimmsten Fall O(n²), weil Strings unveränderlich sind und jede Verkettung das Ganze kopiert. Nutze stattdessen ''.join(chunks) – es baut den String einmal auf.

Sortieren, wenn du es nicht brauchst. sorted() ist O(n log n). Wenn du es in einer Schleife aufrufst, nur um Max oder Min jeder Iteration zu finden, nutze max()/min() (O(n)) oder besser, einen Heap (heapq), wenn du das laufende Extremum wiederholt brauchst. heapq.nlargest(k, data) ist O(n log k), viel billiger als die ganze Liste zu sortieren, wenn k klein ist.

Rekursive Funktionen ohne Memoization. Naives rekursives Fibonacci ist O(2ⁿ), weil es dieselben Subprobleme immer wieder berechnet. Füge functools.lru_cache hinzu und es fällt auf O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Big O schnell aus echtem Code ablesen

Zähle verschachtelte Schleifen über dieselbe Eingabe – das ist normalerweise dein Exponent. Eine einzelne Schleife ist O(n). Eine Schleife in einer Schleife ist O(n²), es sei denn, der Bereich der inneren Schleife schrumpft (wie bei der optimierten Form von Bubble Sort, immer noch O(n²) im schlimmsten Fall, aber weniger Vergleiche). Rekursive Aufrufe, die das Problem halbieren, wie Binary Search oder Merge Sort, deuten auf O(log n) oder O(n log n) hin. Rekursive Aufrufe, die pro Ebene in mehrere Aufrufe verzweigen, wie naives Fibonacci, deuten auf exponentielle Zeit hin – ein starkes Signal, dass du Memoization oder eine iterative Umschreibung brauchst.

Gute Gewohnheit: Bevor du verschachtelte Schleifen oder Rekursion über nutzerseitige Daten schreibst, frage dich, was n realistisch in Produktion sein könnte, nicht in deiner Testdatei. Wenn n sechsstellig werden könnte, braucht eine O(n²) Lösung einen zweiten Blick, bevor sie verschickt wird.

Mehr über Komplexitätsanalyse, Sortieralgorithmen und Profiling-Tools findest du in den Python und Computer Science Segmenten auf Korra Studio.