Algorithmische Komplexität und Datenstrukturen
Problem
Deine Anwendung findet einen Kunden, indem sie jeden Datensatz in einer Liste prüft. Bei 1.000 Kunden fühlt sich das sofort an. Bei zehn Millionen Kunden und Hunderten von Suchanfragen pro Sekunde wird derselbe Ansatz aufwendig. Warum verändert mehr Datenmenge die Leistung so stark?
Lösung — Algorithmische Komplexität
Ein Algorithmus ist ein Verfahren zur Lösung eines Problems. Eine Datenstruktur legt fest, wie die Daten organisiert sind. Zusammen bestimmen sie, wie viel Arbeit eine Operation benötigt.
Der Buchstabe n steht für die Anzahl der Eingabeelemente. Bei einer Liste mit 1.000 Kunden ist n also 1.000. Big O beschreibt eine Grenze dafür, wie der Arbeitsaufwand mit wachsendem n zunimmt. Die folgenden Beispiele zählen Prüfungen oder Vergleiche, damit die unterschiedlichen Wachstumsmuster sichtbar werden.
1. O(n): Die Arbeit wächst mit der Anzahl der Elemente
Stell dir eine unsortierte Kundenliste vor. Um den Kunden mit der ID 87 zu finden, prüfst du den ersten Eintrag, dann den zweiten und so weiter, bis du einen Treffer findest.
Steht der Kunde ganz hinten oder fehlt er, prüfst du jeden Eintrag. In diesem schlechtesten Fall sind bis zu n Prüfungen nötig:
1.000 Kunden → bis zu 1.000 Prüfungen 10.000 Kunden → bis zu 10.000 Prüfungen
Zehnmal so viele Kunden können zehnmal so viel Arbeit bedeuten. Das nennt man lineares Wachstum. Ein Treffer am Anfang kann trotzdem schnell gefunden werden.
2. O(log n): Den Suchbereich immer wieder halbieren
Stell dir nun ein nach Kunden-ID sortiertes Array vor. Die binäre Suche prüft den mittleren Eintrag. Ist die gesuchte ID kleiner, geht es in der unteren Hälfte weiter; ist sie größer, in der oberen. Das wiederholt sich, bis die ID gefunden oder der verbleibende Bereich leer ist.
Jede Prüfung schließt ungefähr die Hälfte der verbleibenden Kandidaten aus. Das funktioniert, weil die IDs sortiert sind und ein Array direkten Zugriff auf seine Mitte erlaubt.
1.000 Kunden → höchstens ungefähr 10 Prüfungen 1.000.000 Kunden → höchstens ungefähr 20 Prüfungen
Die Liste ist 1.000-mal größer geworden, die Zahl der Prüfungen hat sich aber nur ungefähr verdoppelt. Der Logarithmus zählt hier die wiederholten Halbierungen; du musst ihn nicht von Hand berechnen. Eine Verdoppelung der Datenmenge bedeutet ungefähr eine zusätzliche Prüfung.
3. Erwartetes O(1): Der durchschnittliche Aufwand bleibt ungefähr konstant
Stell dir eine Hashtabelle vor, die Kunden-IDs den Kundendatensätzen zuordnet. Beim Einfügen bestimmt die Tabelle mithilfe einer Hashfunktion, wo ein Eintrag abgelegt wird. Später hilft dieselbe Funktion dabei, den Eintrag zu dieser ID zu finden.
Bei einer gut verwalteten Tabelle und IDs fester Größe prüft eine Suche im Durchschnitt nur wenige mögliche Einträge, anstatt die gesamte Sammlung durchzugehen.
1.000 Kunden → ungefähr konstanter durchschnittlicher Suchaufwand 1.000.000 Kunden → ungefähr konstanter durchschnittlicher Suchaufwand
Die 1 bedeutet, dass der erwartete Aufwand beim Wachsen der Sammlung begrenzt bleibt. Sie bedeutet nicht genau eine CPU-Anweisung. „Erwartet“ beschreibt einen Durchschnitt unter den Annahmen der Hashverteilung und keine Zusage für jede einzelne Suche. Gemeint ist das Nachschlagen eines Eintrags, nachdem die Tabelle aufgebaut wurde.
4. O(n²): Elemente werden mit anderen Elementen verglichen
Stell dir vor, du prüfst jedes Paar von Kundendatensätzen auf ein mögliches Duplikat. Jeder Datensatz wird mit allen anderen verglichen, wobei jedes Paar nur einmal geprüft wird.
Bei drei Datensätzen A, B und C sind die Paare A–B, A–C und B–C. Mit weiteren Datensätzen wächst die Zahl der Paare schnell:
10 Datensätze → 45 verschiedene Paare 100 Datensätze → 4.950 verschiedene Paare 200 Datensätze → 19.900 verschiedene Paare
Von 100 auf 200 Datensätze vervierfacht sich die Zahl der Vergleiche ungefähr. Das ist quadratisches Wachstum: Der Aufwand wächst proportional zum Quadrat von n. Die genaue Zahl verschiedener Paare lautet n × (n − 1) ÷ 2; Big O fasst dieses Wachstum als O(n²) zusammen.
Kerngedanke: O(n) wächst mit der Liste, O(log n) mit wiederholten Halbierungen, erwartetes O(1) bleibt im Durchschnitt ungefähr konstant, und O(n²) wächst mit der Zahl der Paare.