Komplexität und O-Notation
Warum ein Programm mit 1000 Datensätzen in Millisekunden fertig ist und mit einer Million erst nach Stunden: wie man das Wachstum von Rechenaufwand beschreibt, welche Klassen es gibt und wo sich in Java-Code versehentlich quadratischer Aufwand versteckt.
Die O-Notation beschreibt, wie der Aufwand eines Algorithmus wächst, wenn die Eingabe größer wird – nicht, wie lange er in Sekunden braucht. O(n) heißt: doppelt so viele Daten, etwa doppelt so viel Arbeit. O(n²) heißt: doppelt so viele Daten, viermal so viel Arbeit. Konstante Faktoren fallen weg, nur die Wachstumsform zählt.
Für die Praxis entscheidend: Bei kleinen Datenmengen ist fast alles schnell. Der Unterschied zwischen O(n) und O(n²) zeigt sich erst bei Tausenden oder Millionen Einträgen – dann aber dramatisch. Die meisten Performance-Katastrophen im Alltag sind versehentlich quadratischer Code, etwa ein list.contains() in einer Schleife.
Wie schnell wächst der Aufwand?
Angenommen, ein Rechner schafft eine Milliarde einfache Schritte pro Sekunde. Wie lange brauchen Algorithmen verschiedener Klassen? Schieb die Datenmenge hoch:
| Klasse | Name | Typisches Beispiel |
|---|---|---|
O(1) | konstant | Array-Zugriff per Index, HashMap.get im Normalfall |
O(log n) | logarithmisch | binäre Suche, Suche im B-Baum einer Datenbank, TreeMap.get |
O(n) | linear | einmal alles durchgehen, Maximum suchen |
O(n log n) | „n log n“ | gutes Sortieren – schneller geht es mit Vergleichen nicht |
O(n²) | quadratisch | jedes Element mit jedem vergleichen, zwei verschachtelte Schleifen |
O(2ⁿ) | exponentiell | alle Teilmengen ausprobieren |
O(n!) | fakultät | alle Reihenfolgen ausprobieren – etwa alle Routen einer Rundreise |
Was die O-Notation weglässt
Formal ist O(f(n)) eine obere Schranke: Ab einer gewissen Größe wächst der Aufwand höchstens wie f(n), mal einer Konstante. Deshalb sind 3n + 50 und n beide O(n), und die Basis des Logarithmus spielt keine Rolle. Das macht die Notation handlich – und führt in die Irre, wenn die Konstante riesig ist. Ein O(n)-Algorithmus, der bei jedem Schritt auf die Festplatte wartet, verliert gegen einen O(n log n)-Algorithmus im Cache, solange n nicht astronomisch ist. Die Speicherhierarchie ist so eine versteckte Konstante.
Außerdem unterscheidet man schlechtesten Fall, Durchschnittsfall und amortisierte Kosten. Quicksort ist im Durchschnitt O(n log n), im schlechtesten Fall O(n²). Ein HashMap.get ist im Durchschnitt O(1) – solange die Hashes gut verteilt sind.
Die Macht des Logarithmus
Ein Telefonbuch mit einer Million Namen: Wer Seite für Seite sucht, braucht im Schnitt eine halbe Million Blicke. Wer in der Mitte aufschlägt und je nach Buchstabe die vordere oder hintere Hälfte nimmt, braucht höchstens 20. Jeder Schritt halbiert den Rest – das ist binäre Suche, und sie funktioniert nur auf sortierten Daten.
Amortisiert: warum ArrayList.add trotzdem O(1) ist
Eine ArrayList speichert ihre Elemente in einem Array fester Größe. Ist es voll, legt sie ein größeres an und kopiert alles um – das kostet O(n). Trotzdem gilt add als O(1). Der Trick: Das Array wächst nicht um eins, sondern um die Hälfte. Teure Kopien werden dadurch immer seltener. Füge Elemente hinzu:
Über viele Aufrufe gemittelt kostet jedes add nur eine kleine, feste Zahl von Kopien – das ist amortisiert O(1). Einzelne Aufrufe können trotzdem teuer sein. Wer vorher weiß, wie viele Elemente kommen, gibt die Kapazität gleich mit: new ArrayList<>(10_000).
P, NP und Probleme ohne schnelle Lösung
Manche Probleme scheinen grundsätzlich keine schnelle Lösung zu haben. Die Theorie teilt sie grob ein:
Schnell lösbar
Probleme, die sich in polynomieller Zeit lösen lassen – O(n), O(n²), O(n³). Sortieren, kürzeste Wege, Suchen.
Schnell prüfbar
Eine vorgeschlagene Lösung lässt sich schnell prüfen – aber finden? Ein ausgefülltes Sudoku zu prüfen ist leicht, eines zu lösen bei beliebiger Größe schwer.
P = NP?
Ob jedes schnell prüfbare Problem auch schnell lösbar ist, weiß niemand. Es ist eine der berühmtesten offenen Fragen der Mathematik, ausgeschrieben mit einer Million Dollar Preisgeld.
Die schwersten Probleme in NP heißen NP-vollständig: Fände man für eines einen schnellen Algorithmus, hätte man ihn für alle. Dazu gehören Stundenpläne, Tourenplanung, das Packen von Containern, viele Konfigurationsprobleme. In der Praxis löst man sie trotzdem – nur nicht garantiert optimal: mit Heuristiken, Näherungsverfahren oder spezialisierten Lösern, die typische Fälle schnell schaffen. Wer im Projekt merkt, dass sein Problem NP-vollständig ist, sucht besser eine gute statt der perfekten Lösung.
Für Entwickler übersetzt
| Operation | Aufwand | Anmerkung |
|---|---|---|
ArrayList.get(i) | O(1) | direkter Array-Zugriff |
ArrayList.add(x) | O(1) amortisiert | gelegentlich Umkopieren |
ArrayList.add(0, x), remove(0) | O(n) | alles dahinter wird verschoben – dafür gibt es ArrayDeque |
List.contains(x) | O(n) | durchsucht die ganze Liste |
LinkedList.get(i) | O(n) | läuft die Kette entlang |
HashMap.get, HashSet.contains | O(1) im Mittel | bei vielen Kollisionen seit Java 8 höchstens O(log n) |
TreeMap.get, TreeSet.add | O(log n) | sortiert, Bereichsabfragen möglich |
PriorityQueue.offer, poll | O(log n) | peek ist O(1) |
List.sort, Arrays.sort | O(n log n) | bei Objekten TimSort, nutzt vorsortierte Abschnitte |
// Versehentlich O(n²): contains auf einer Liste, in einer Schleife
List<String> ohneDoppelte = new ArrayList<>();
for (String s : eingaben)
if (!ohneDoppelte.contains(s)) ohneDoppelte.add(s);
// O(n): ein Set – LinkedHashSet behält dabei die Reihenfolge
List<String> ohneDoppelte = List.copyOf(new LinkedHashSet<>(eingaben));
// Versehentlich O(n²): String-Verkettung in einer Schleife kopiert jedes Mal alles
String text = "";
for (String zeile : zeilen) text += zeile + "\n";
// O(n)
String text = String.join("\n", zeilen);Bei 100 Elementen ist all das egal. Bei 100 000 macht es den Unterschied zwischen Millisekunden und Minuten. Ein guter Reflex beim Code-Review: Steht in einer Schleife ein Aufruf, der selbst eine Schleife ist – contains, indexOf, remove(Object), eine Datenbankabfrage?