Leitfaden zur Big-O-Notation und Zeitkomplexität: Intuition und Mathematik

Die Analyse der Zeitkomplexität bietet eine Möglichkeit, die Effizienz von Algorithmen zu untersuchen und vorherzusagen – unabhängig von der Programmiersprache, in der wir sie umsetzen, und der Hardware, auf der sie laufen.

Ziel der Zeitkomplexitätsanalyse ist nicht, die exakte Laufzeit eines Algorithmus vorherzusagen, sondern diese Fragen beantworten zu können:

1. Wenn zwei Algorithmen dasselbe Problem lösen: Welcher läuft voraussichtlich schneller, wenn beide die gleiche Datenmenge erhalten?
2. Was passiert mit der Ausführungszeit, wenn wir die Datenmenge verdoppeln? Skaliert sie linear und verdoppelt sich ebenfalls? Bleibt sie gleich? Oder etwas ganz anderes?

Am Ende dieses Artikels weißt du, wie du die Zeitkomplexität eines Algorithmus analysierst und diese Fragen beantwortest.

Ist Zeitkomplexität 2024 noch relevant?

Computer werden immer schneller, da liegt die Frage nahe, ob man sich überhaupt noch um Zeitkomplexität kümmern muss. Ein Supercomputer kann doch heutzutage jedes Problem bewältigen – egal, welchen Algorithmus wir verwenden, oder?

Ganz so einfach ist es nicht. Der KI-Boom beruht zwar zu großen Teilen auf massiven Hardware-Fortschritten der letzten Jahre. Aber selbst auf modernster Hardware können einfache Probleme katastrophal langsam werden, wenn man einen schlechten Algorithmus wählt.

Stell dir beispielsweise vor, du würdest eine Datenbanktabelle mit zehn Millionen Einträgen mit einem naiven Algorithmus sortieren. Selbst auf einem modernen Rechner würde dieser vermeintlich einfache Vorgang mehrere Tage dauern – die Datenbank wäre praktisch unbrauchbar. Mit einem effizienten Algorithmus dauert das hingegen weniger als eine Zehntelsekunde.

Grundoperationen und Basisanweisungen

Wir analysieren einen Algorithmus im Random-Access-Machine-Modell (RAM- oder RA-Modell). Dieses Modell nimmt an, dass die folgenden Operationen genau einen Zeitschritt benötigen:

• Arithmetische Operationen
• Logische Vergleiche (<, >, == usw.)
• Anweisungen wie if oder return
• Zugriff auf eine Speicheradresse, z. B. Schreiben oder Lesen eines Variablenwerts

Diese Operationen heißen Grundoperationen. Eine Codezeile, die eine konstante Anzahl solcher Grundoperationen ausführt, nennt man eine Basisanweisung.

Weil die Anzahl der Operationen in einer Basisanweisung konstant ist, hängt sie nicht von der Datenmenge ab. Da uns interessiert, wie die Ausführungszeit mit wachsender Datenmenge wächst, konzentrieren wir uns darauf, wie viele Basisanweisungen der Algorithmus ausführt.

Funktionsaufrufe und Schleifen wie for und while bewertet man, indem man die Basisanweisungen in ihrem Inneren aufsummiert. Betrachte folgenden Code, der die Elemente einer Liste aufsummiert.

def sum_list(lst):
  total = 0          # 1 instruction
  for value in lst:    
    total += value   # executed len(lst) times
  return total       # 1 instruction

Wir haben jeder Zeile Kommentare hinzugefügt, um die Anzahl der Basisanweisungen zu veranschaulichen. Wenn N die Länge von lst ist, ergibt sich insgesamt 1 + N + 1 = N + 2 Basisanweisungen.

Big-O-Notation

Stell dir vor, wir haben zwei Sortieralgorithmen. Wir haben die Anzahl der Basisanweisungen berechnet und erhalten folgende Ausdrücke:

Auf den ersten Blick ist nicht klar, welcher besser skaliert. Die Big-O-Notation vereinfacht solche Ausdrücke mit folgenden Regeln:

1. Terme mit niedrigeren Exponenten weglassen
2. Multiplikative Konstanten ignorieren

Wenden wir das auf beide Ausdrücke an, bleibt in beiden Fällen N2 übrig:

Der vereinfachte Ausdruck ist die Zeitkomplexität des Algorithmus und wird mit O() notiert. Hier können wir schreiben: 4N2 + 2N + 7 = O(N2) und 3N2 + 5N + 13 = O(N2). Beide Algorithmen haben also die gleiche Zeitkomplexität, proportional zum Quadrat der Anzahl der Listenelemente.

Oben haben wir berechnet, dass der Algorithmus sum_list N + 2 Operationen ausführt, wobei N die Listenlänge ist. Nach derselben Vereinfachung bleibt N, also ist die Zeitkomplexität von sum_list O(N).

Das bedeutet, die Laufzeit ist proportional zur Listengröße. Das ist erwartbar: Verdoppeln wir die Anzahl der Elemente, verdoppelt sich der Rechenaufwand – nicht weniger, nicht mehr.

Big-O-Notation: Intuitive Erklärung

Wir können die niedrigergradigen Terme ignorieren, weil ihr Anteil an der Summe mit wachsendem N im Vergleich zum führenden Term verschwindet. Die folgende Grafik zeigt den Beitrag der drei Terme 4N2, 2N und 7 zur Gesamtsumme.

Der quadratische Term 4N2 dominiert sehr schnell nahezu vollständig – selbst bei kleinen N. Daher sind bei großen Datenmengen die niedrigeren Terme gegenüber dem führenden Term vernachlässigbar.

Die multiplikative Konstante lassen wir weg, weil sie unabhängig von der Datenmenge ist.

Big-O-Notation: Mathematische Definition

Die obigen Schritte reichen in der Praxis meist aus, um die Zeitkomplexität korrekt herzuleiten. Wir zählen die Basisanweisungen eines Algorithmus und erhalten einen Ausdruck f(N). Nach den beiden Vereinfachungen erhalten wir einen Ausdruck g(N). Dann schreiben wir f(N) = O(g(N)). Man liest: „f ist big O von g“.

Das ist jedoch keine formale Definition und in manchen Fällen nicht ausreichend.

Mathematisch gilt für eine positive Funktion f(N) = O(g(N)), wenn es eine Konstante C gibt, sodass für große N Folgendes gilt:

f(N) ≤ C × g(N)

Damit können wir zeigen, dass f(N) = 4N2 + 2N + 7 = O(N2) ist. Hier können wir C = 5 wählen und sehen, dass für jedes N > 4  f(N) ≤ 5 × N2 gilt:

In der Praxis verwenden wir einfach die oben genannten Vereinfachungsregeln.

Arten von Zeitkomplexität

Jetzt, da die Grundlagen der Big-O-Notation klar sind, schauen wir uns gängige Zeitkomplexitäten und ihre Auswirkungen an – beginnend mit der effizientesten: konstanter Zeit.

Konstante Zeit: O(1)

Wie der Name sagt, hängt die Laufzeit bei Algorithmen in konstanter Zeit nicht von der Datenmenge ab. Typisch sind Berechnungen mit fester Zahl an Eingaben, etwa die Distanz zwischen zwei Punkten.

Die Distanz zwischen zwei Punkten berechnet man über die Quadratwurzel der quadrierten Differenzen der x- und y-Koordinaten der beiden Punkte.

Die unten gezeigte Funktion dist berechnet diese Distanz. Sie besteht aus drei Basisanweisungen, also einer Konstante. Die Zeitkomplexität ist hier O(1).

def dist(p, q):
  dx = (p[0] - q[0]) ** 2  # 1 instruction
  dy = (p[1] - q[1]) ** 2  # 1 instruction
  return (dx + dy) ** 0.5  # 1 instruction

Interessant ist, dass eine Funktion auch bei großen Datenmengen O(1) sein kann. Die Länge einer Liste mit len zu bestimmen, ist O(1), weil die Implementierung die Größe intern mitführt und die Elemente nicht jedes Mal neu zählen muss.

Lineare Zeit: O(N)

sum_list haben wir bereits als Beispiel für lineare Zeit gesehen. Generell benötigen lineare Algorithmen einen Durchlauf über alle Datenpunkte. Typische Operationen sind Minimum, Maximum oder Durchschnitt berechnen.

Üben wir das mit der folgenden Funktion, die das Minimum einer Liste berechnet:

def minimum(lst):
  min_value = lst[0]                    # 1 instruction
  for i in range(1, len(lst)):
    min_value = min(min_value, lst[i])  # executed len(lst) - 1 times
  return min_value                      # 1 instruction

Hat die Liste N Elemente, ist die Komplexität 1 + (N - 1) + 1 = N + 1 = O(N).

Die Laufzeit wächst also proportional zur Datenmenge. Verdoppeln wir die Daten, verdoppelt sich auch die Laufzeit.

Logarithmische Zeit: O(log(N))

Beim Zahlenratespiel soll eine versteckte Zahl zwischen 1 und N mit möglichst wenigen Versuchen erraten werden. Nach jedem Tipp erhalten wir die Rückmeldung, ob die Zahl höher, niedriger oder gleich unserem Tipp ist. Ist sie gleich, gewinnen wir, sonst raten wir weiter.

Eine effektive Strategie ist, stets die Mitte zu tippen. Angenommen N = 15. Dann wäre unser erster Tipp 8. Ist die geheime Zahl kleiner als 8, liegt sie zwischen 1 und 7. Ist sie größer, liegt sie zwischen 9 und 15. So fahren wir fort, bis die richtige Zahl gefunden ist. Die Abbildung zeigt mögliche Pfade dieser Strategie.

Betrachten wir die Zeitkomplexität dieser Vorgehensweise. Anders als zuvor hängt die Anzahl der Schritte nicht nur von N ab, da wir theoretisch auch sofort richtig liegen könnten.

Bei der Analyse konzentrieren wir uns jedoch auf das Worst-Case-Szenario. Für N = 15 brauchen wir im schlechtesten Fall 4 Versuche. Jeder Tipp halbiert den verbleibenden Suchraum. Im Worst Case raten wir weiter, bis nur eine Möglichkeit übrig bleibt. Die zentrale Frage ist daher:

Wie oft müssen wir N durch 2 teilen, um 1 zu erhalten?

Die Antwort ist der Logarithmus zur Basis 2 von N, also log2(N). Der zugrunde liegende Algorithmus heißt Binärsuche. Da die maximale Anzahl an Versuchen log2(N) ist, schreiben wir die Komplexität als O(log2(N)) bzw. kurz O(log(N)), da Konstanten in der Notation keine Rolle spielen.

Logarithmische Zeit wächst extrem langsam und ist in der Praxis fast so gut wie konstant. Selbst für große N bleibt die Anzahl der Operationen gering. Bei N = 1 Milliarde sind es beispielsweise nur rund 30 Schritte.

Die Binärsuche ist ein Grundbaustein der Informatik mit vielen Anwendungen. In der Sprachverarbeitung etwa können Rechtschreibprüfung und Autokorrektur Varianten der Binärsuche nutzen, um Kandidatenwörter effizient zu finden.

Quadratische Zeit: O(N2)

Sortieren ist eine grundlegende Aufgabe, die Computer häufig ausführen. Eine Methode, eine Liste mit N Zahlen zu sortieren, ist, wiederholt das Minimum zu finden.

def selection_sort(lst):
  sorted_lst = []              # 1 instruction
  for _ in range(len(lst)):
    minimum = min(lst)         # executed len(lst) times
    lst.remove(minimum)        # executed len(lst) times
    sorted_lst.append(minimum) # executed len(lst) times
  return sorted_lst            # 1 instruction

Zur Analyse einer for-Schleife bewerten wir die Komplexität der Anweisungen darin und multiplizieren mit der Anzahl der Iterationen.

Das Minimum einer Liste zu bestimmen und ein Element zu entfernen sind jeweils O(N). Anhängen ist O(1). Jede Iteration hat also O(N + N + 1) = O(2N + 1), vereinfacht O(N). Da es N Iterationen gibt, ist die Komplexität N × O(N) = O(N2). Der Rest von selection_sort() besteht aus drei einfachen Anweisungen, also insgesamt O(N2 + 3) = O(N2).

Unsere Schleifenanalyse war etwas grob. Pro Iteration entfernen wir ein Element, daher führen nicht alle Iterationen gleich viele Anweisungen aus. Die erste Iteration hat N, die zweite N - 1, die dritte N - 2, …, die letzte nur 1.

Die tatsächliche Summe lautet also:

N + (N - 1) + (N - 2) + … + 1 

Diese Summe ist gleich (N2 + N) / 2. Allerdings

(N2 + N) / 2 = ½N2 + ½N = O(N2)

Obwohl wir zuvor überzählt haben, bleibt die Gesamtkomplexität quadratisch. selection_sort() steht damit für einen langsamen Sortieralgorithmus mit O(N2).

Quadratische Algorithmen skalieren schlecht: Für Millionen Datenpunkte sind sie unpraktisch – eine Verdopplung der Datenmenge vervierfacht die Laufzeit.

Loglineare Zeit: O(N log(N))

Es gibt Sortieralgorithmen mit O(N log(N)), z. B. Merge Sort. Wir gehen hier nicht ins Implementierungsdetail. Wenn du mehr erfahren willst, findest du eine kurze Einführung zu Merge Sort im Kurs Data Structures and Algorithms in Python.

Wie erwähnt, verhält sich der logarithmische Anteil in der Praxis fast wie konstant. Daher kann ein O(N log(N))–Algorithmus in realen Anwendungen ähnlich schnell sein wie ein linearer.

Die folgende Grafik zeigt: N log(N) und N wachsen ähnlich, während N2 sehr schnell wächst und dadurch bald sehr langsam wird.

Kubische Zeit: O(N3)

Ein in der KI weit verbreiteter Algorithmus mit kubischer Komplexität ist die Matrixmultiplikation – zentral für große Sprachmodelle wie GPT, sowohl im Training als auch in der Inferenz.

Um zwei N×N-Matrizen A und B zu multiplizieren, multipliziert man jede Zeile von A mit jeder Spalte von B. Der Eintrag (i, j) des Produkts ist die Summe der Produkte der Elemente aus Zeile i von A und Spalte j von B.

Hier ist eine Python-Implementierung der Matrixmultiplikation:

def matrix_mul(A, B):
  n = len(A)                                       # 1 instruction
  res = [[0 for _ in range(n)] for _ in range(n)]  # N^2 instructions
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += A[i][k] * B[k][j]             # executed N×N×N = N^3 times
  return res                                       # 1 instruction

In Summe führt matrix_mul() N3 + N2 + 2 Anweisungen aus, die Zeitkomplexität ist also O(N3).

Alternativ können wir über die Berechnungen argumentieren: Das Ergebnis hat N2 Einträge. Jeder Eintrag braucht O(N), also insgesamt N2 × O(N) = O(N3).

Kubische Algorithmen sind sehr langsam. Verdoppeln wir die Datenmenge, verachtfacht sich die Laufzeit. Schon bei moderaten N explodiert die Anzahl der Anweisungen.

Matrixmultiplikation ist ein Beispiel, bei dem Hardware-Fortschritte entscheidend waren. Es gibt zwar etwas effizientere Verfahren, aber vor allem speziell für Matrixmultiplikation ausgelegte GPUs haben das Training großer Modelle wie GPT überhaupt erst in vertretbaren Zeiten ermöglicht.

Kürzlich wurde sogar erforscht, Matrixmultiplikation in großen Lernmodellen zu vermeiden – mehr dazu im Artikel MatMul-Free LLMs: Key Concepts Explained.

Exponentielle Zeitkomplexität: O(2N) und O(N!)

Exponentielle Algorithmen entstehen oft, wenn man alle möglichen Lösungen durchprobiert. Plane etwa eine Route für einen Lieferwagen mit N Stopps. Eine Herangehensweise ist, jede mögliche Reihenfolge zu bewerten. Das Python-itertools-Paket bietet eine einfache Möglichkeit, alle Permutationen einer Liste zu erzeugen.

import itertools
for order in itertools.permutations([1, 2, 3]):
  print(order)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Die Anzahl der Permutationen einer Liste der Länge N ist N! („N Fakultät“). Die Fakultätsfunktion wächst exponentiell. Für N = 13 übersteigt die Anzahl der Permutationen bereits 1 Milliarde.

Sind die Stopps als Liste von 2D-Punkten gegeben, können wir die Reihenfolge mit minimaler Gesamtdistanz finden, indem wir alle möglichen Sequenzen durchgehen und die beste merken.

def optimize_route(locations):
  minimum_distance = float("inf")                  # 1 instruction
  best_order = None                                # 1 instruction
  for order in itertools.permutations(locations):  # N! iterations
    distance = 0                                   # 1 instruction, N! times
    for i in range(1, len(order)):                 
      distance += dist(order[i - 1], order[i])     # N-1 instructions, N! times
    if distance < minimum_distance:                
      distance = minimum_distance                  # 1 instruction, N! times
      best_order = order                           # 1 instruction, N! times
  return best_order                                # 1 instruction

Die äußere for-Schleife läuft N! Mal. Die Anzahl der Operationen in optimize_route() ist daher N! × (1 + N - 1 + 2) + 3 = N! × (N + 2) + 3 = N! × N + 2N! + 3.

Wir haben gelernt, bei der Zeitkomplexität niedrigergradige Terme zu ignorieren. Hier tritt jedoch N! auf, das keine Potenz von N ist. Wir verallgemeinern unsere Regel und lassen die Terme mit langsamerem Wachstum weg. Die folgende Tabelle ordnet gängige Terme nach Wachstumsgeschwindigkeit (von langsam nach schnell):

Somit lässt sich die Zeitkomplexität von optimize_route() als N! × N + 2N! + 3 = O(N! × N) schreiben.

Exponentielle Algorithmen sind in der Regel nur für sehr kleine Instanzen praktikabel. Bereits bei 13 Stopps gibt es über 1 Milliarde Permutationen – für die Praxis unbrauchbar.

Zeitkomplexität: Worst Case und Best Case

Beim Zahlenratespiel haben wir den Worst Case betrachtet. So stellen wir sicher, dass die Wachstumsrate der Laufzeit garantiert nicht unterschritten wird.

Im Best Case raten wir sofort richtig – die Best-Case-Komplexität ist O(1). Das stimmt zwar, ist aber wenig hilfreich, weil es sehr unwahrscheinlich ist.

Grundsätzlich betrachten wir bei der Analyse daher den Worst Case, weil:

1. Leistung garantiert: Der Worst-Case liefert eine obere Schranke. Das ist essenziell für Anwendungen mit harten Anforderungen, z. B. Echtzeitsysteme.
2. Sicherheit und Verlässlichkeit: Worst-Case-Analyse hilft, robuste Algorithmen zu entwerfen, die auch in extremen Situationen innerhalb akzeptabler Grenzen funktionieren.
3. Obere Schranke: Die Worst-Case-Komplexität gibt eine Obergrenze für Zeit- und Speicherbedarf.

Zeitkomplexität: Praxisrelevanz

Zeitkomplexität wirkt theoretisch, ist in der Praxis aber äußerst nützlich.

Wenn eine Funktion dauerhaft nur kleine Datenmengen verarbeitet, kann ein leicht verständlicher O(N2)-Algorithmus sinnvoller sein als ein komplexer, schwer wartbarer O(N)-Algorithmus. Das sollte jedoch eine bewusste Entscheidung sein, um nicht böse überrascht zu werden, wenn die Anwendung plötzlich mehr Traffic verarbeiten muss.

Die Analyse zeigt auch: Kleine Code-Mikrooptimierungen bringen meist wenig. Große Sprünge erreicht man, indem man die Anzahl der nötigen Grundoperationen grundsätzlich reduziert. Sauberer, verständlicher Code ist in der Regel besser als überoptimierter, unlesbarer Code.

Die langsamsten Teile dominieren die Gesamtlaufzeit. Es ist meist sinnlos, zuerst die schnelleren Teile zu optimieren. Angenommen, wir haben eine Funktion mit zwei Schritten:

def process_data(data):
  clean_data(data)
  analyze_data(data)

Hat clean_data() O(N2) und analyze_data() O(N3), verbessert eine Optimierung von clean_data() die Gesamtlaufzeit von process_data() nicht wesentlich. Es ist sinnvoller, analyze_data() zu verbessern.

Zudem kann die Zeitkomplexität Hardware-Entscheidungen beeinflussen. Ein O(N3)-Algorithmus skaliert zwar schlecht, kann aber bei kleinen Datenmengen auf starker Hardware oder in einer schnelleren Sprache ausreichend schnell sein. Hat ein Algorithmus jedoch exponentielle Komplexität O(2N), hilft kein Hardware-Upgrade – dann braucht es einen effizienteren Algorithmus.

Fazit

Trotz schnellerer Computer verarbeiten wir heute mehr Daten denn je. Jedes Mal, wenn wir Internet, Smartphones oder smarte Geräte nutzen, entsteht gewaltig viel Information. Je größer dieser Datenberg, desto anspruchsvoller wird es, das Wichtige zu finden. Umso wichtiger ist es, unsere Werkzeuge – vor allem Algorithmen – fit zu machen, um all diese Informationen effizient zu verarbeiten und zu verstehen.

Die Analyse der Zeitkomplexität liefert ein klares Rahmenwerk, um über Laufzeiten zu argumentieren. Ziel ist es, die Wachstumsrate zu verstehen – nicht exakte Zeiten vorherzusagen. Trotz ihrer Vereinfachungen ist sie in der Praxis äußerst nützlich und erfasst das Wesen des Laufzeitverhaltens sehr gut.

Wenn du weitere Informatikthemen erkunden willst, lies meinen Artikel Data Structures: A Comprehensive Guide With Python Examples.