Big-O anhand von Code-Beispielen: Algorithmus-Komplexität leicht verstehen

1. Übersicht

Big-O ist eine Methode, um die Wachstumsrate der Laufzeit (oder des Speicherverbrauchs) zu beschreiben, wenn die Eingabegröße zunimmt. Dieser Artikel verwendet keine trockenen mathematischen Formeln, sondern geht durch die gängigsten Komplexitätsstufen anhand echter Java-Code-Beispiele durch und analysiert, welche Zeilen Kosten verursachen. Nach dem Lesen wirst du einen Code-Ausschnitt anschauen und sofort erraten können, ob er O(1), O(n), O(n log n) oder O(n²) ist, ohne per Hand zu zählen.

2. Was ist Big-O und warum sollte man sich dafür interessieren

Big-O beantwortet die Frage: „Wenn die Eingabe sich verdoppelt, wie sehr wächst die Laufzeit?” Es ignoriert Konstanten und kleine Faktoren und behält nur die Wachstumstendenz bei, wenn n (die Eingabegröße) gegen unendlich geht.

n = 1.000      -> O(n) führt ~1.000 Schritte aus
n = 1.000.000  -> O(n) führt ~1.000.000 Schritte aus (wächst linear)
n = 1.000.000  -> O(n²) führt ~10^12 Schritte aus (wächst extrem schnell)

Zwei Code-Ausschnitte können „auf den ersten Blick gleich aussehen”, aber die Komplexität unterscheidet sich völlig, wenn eine Seite verschachtelte Schleifen in aufgerufenen Funktionen versteckt. Big-O zu verstehen hilft dir, Code zu vermeiden, der mit 100 Test-Datensätzen gut läuft, aber „hängt fest” wenn man mit 10 Millionen Datensätzen in die Produktion geht.

Anmerkung: Big-O beschreibt den schlechtesten Fall (worst case) nach der am weitesten verbreiteten Konvention, es sei denn, es ist explizit best-case oder average-case angegeben.

3. O(1) – Konstante Zeit

Die Laufzeit ist unveränderlich, unabhängig von der Eingabegröße.

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get ist O(1) im Durchschnitt
    }
}

get() auf HashMap berechnet den Hash des Schlüssels und springt direkt zum entsprechenden Bucket, unabhängig von der Anzahl der Elemente in der Map. Ebenso ist der Zugriff auf array[i] oder list.get(i) mit ArrayList auch O(1), da nur die Offset-Adresse berechnet werden muss.

4. O(n) – Lineare Zeit

Die Laufzeit wächst proportional zur Eingabegröße.

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // stoppe früh, aber worst-case durchläuft die gesamte Liste
            }
        }
        return false;
    }
}

Die for-Schleife durchläuft maximal n Elemente von orders. Der schlechteste Fall tritt auf, wenn kein Auftrag abgelaufen ist, wodurch die gesamte Liste überprüft werden muss. Das ist das klassische O(n)-Muster: eine einzelne Schleife, nicht verschachtelt.

4.1. Häufige Fallstricke: contains() in der Schleife

public class DuplicateChecker {

    // O(n²) weil contains() auf List O(n) ist und n-mal aufgerufen wird
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

seen.contains(email) auf ArrayList ist O(n), da eine lineare Suche erforderlich ist. Das Aufrufen innerhalb der for-Schleife macht die gesamte Funktion zu O(n²) — ein sehr leicht zu begehender Fehler, wenn man die interne Datenstruktur nicht beachtet.

public class DuplicateChecker {

    // O(n) dank HashSet mit O(1) für add/contains
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // add() gibt false zurück, wenn es bereits vorhanden ist
                return true;
            }
        }
        return false;
    }
}

Allein durch das Wechseln von List zu HashSet sinkt die Komplexität von O(n²) auf O(n). Dies ist das praktischste Beispiel, das zeigt, dass die Wahl der richtigen Datenstruktur wichtiger ist als „Mikro-Optimierung”.

5. O(log n) – Logarithmische Zeit

Jeder Schritt eliminiert die Hälfte des Suchraums.

public class PriceLookup {

    // sortedPrices muss vorher aufsteigend sortiert sein
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Binary Search halbiert das Array bei jeder while-Schleife. Mit n = 1.000.000 sind daher nur etwa 20 Schritte erforderlich (log₂ 1.000.000 ≈ 20), um das Ergebnis zu finden, anstatt eine Million Elemente linear zu durchlaufen.

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

Dieser Test bestätigt das richtige Verhalten sowohl wenn gefunden (gibt Index zurück) als auch wenn nicht gefunden (gibt -1 zurück) — die zwei wichtigsten Branches der Binary Search.

6. O(n log n) – Kombination aus linear und logarithmisch

Dies ist die Komplexität effizienter Sortieralgorithmen wie merge sort, quick sort (average case) oder Collections.sort().

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Collections.sort()/List.sort() in Java verwendet Timsort (eine Variante von merge sort) und garantiert O(n log n) im schlechtesten Fall. Wenn du siehst, dass Code sort() innerhalb einer Schleife aufruft, die n-mal läuft, wird die Gesamtkomplexität zu O(n² log n) multipliziert — ein Zeichen, dass eine Umstrukturierung erforderlich ist.

7. O(n²) – Quadratische Zeit

Zwei verschachtelte Schleifen, jede durchläuft die gesamte (oder fast die gesamte) Eingabe.

public class PairFinder {

    // Finde alle Produktpaare, deren Preissumme target entspricht
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

Die äußere Schleife läuft n-mal, die innere Schleife läuft maximal n-mal für jede Iteration der äußeren Schleife — die Gesamtanzahl der Vergleiche ist ungefähr n²/2, daher ist die Komplexität O(n²). Mit n = 10.000 sind das 50 Millionen Vergleiche — es läuft immer noch, aber es ist deutlich langsam.

public class PairFinder {

    // O(n) dank HashSet mit O(1) für add/contains
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

Anstatt jedes Paar zu vergleichen, brauchen wir nur eine einzelne Schleife und O(1)-Lookups in einem HashSet. Dies ist die weit verbreitete Technik „Zeit gegen Speicher tauschen”: wir verbrauchen zusätzlichen Speicher für seen, aber reduzieren die Komplexität von O(n²) auf O(n).

8. O(2^n) – Exponentielle Zeit

Die Laufzeit verdoppelt sich jedes Mal, wenn die Eingabe um 1 Einheit wächst — häufig bei rekursiven Funktionen, die alle Teilmengen berechnen.

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Branch 1: element nicht wählen
        backtrack(items, index + 1, current, result);

        // Branch 2: element wählen
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Jedes Element erzeugt 2 rekursive Branches (wählen oder nicht wählen), also haben wir mit n Elementen 2^n Teilmengen. Mit n = 20 sind es bereits über 1 Million Teilmengen; mit n = 40 kann keine Maschine in angemessener Zeit fertig werden. Das ist ein Zeichen dafür, dass man eine dynamische Programmierung (dynamic programming) in Betracht ziehen sollte, falls das Problem es erlaubt.

9. Schneller Vergleich mit echten Benchmarks

Ein einfaches Test-Beispiel, um den Unterschied zwischen O(n) und O(n²) „zu sehen”:

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n), also immer noch sehr schnell mit 100k Elementen
    }
}

Wenn du hasDuplicateFast durch hasDuplicateSlow mit denselben 100.000 E-Mails ersetzt, wird die Laufzeit weit über die 500-ms-Grenze hinausgehen — ein anschaulicher Beweis für den Unterschied zwischen O(n) und O(n²) mit echten Daten.

10. Zusammenfassung der Tabelle und Schnellerkennungsregeln

Big-O	Zeichen im Code	Beispiel
O(1)	Keine Schleife, direkter Zugriff (Array-Index, HashMap.get)	map.get(key)
O(log n)	Jeder Schritt eliminiert einen Teil des Suchraums	Binary Search
O(n)	Eine einzelne Schleife durchläuft die Eingabe	for über List
O(n log n)	Schleife mit sort oder Divide-and-Conquer	Collections.sort()
O(n²)	Verschachtelte Schleifen, beide durchlaufen die Eingabe	Jedes Paar vergleichen
O(2^n)	Rekursion mit 2 Branches pro Schritt, keine Pruning	Alle Teilmengen generieren

Schnellzählregel: Zähle die verschachtelten Schleifen die über die Eingabe laufen — jede Schleifenebene fügt einen „Grad n” hinzu. Wenn in der Schleife Bibliotheksfunktionen aufgerufen werden (contains, sort, indexOf), prüfe deren Komplexität, bevor du sie zur Summe addierst.

Anmerkung: Big-O sagt nichts über echte Konstanten aus. Ein O(n)-Algorithmus mit großer Konstante (z.B. Datei-Lesevorgänge in jeder Schleife) könnte langsamer sein als O(n log n) mit kleiner Konstante, wenn n noch nicht groß genug ist. Optimiere Big-O nicht blind, ohne vorher zu profilen.

11. Fazit

Big-O ist ein Werkzeug zum Vorhersagen von Trends, nicht absolute Zahlen — aber genau diese Trends bestimmen, ob dein Code wächst oder zusammenbricht, wenn die Daten wachsen. Der praktischste Tipp: Frage dich jedes Mal, wenn du eine Schleife schreibst, „rufe ich irgendeine O(n)-Funktion in dieser Schleife auf?” — das ist der Ursprung der meisten unerwünschten O(n²)-Fehler in der Praxis. Die 6 oben genannten Komplexitätsstufen gut zu beherrschen ist ausreichend, um die meisten Algorithmen-Codes, die du täglich triffst, zu verstehen und zu hinterfragen.