Big-O-Notation: Zeitkomplexität

Codeoptimierung in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Was ist Zeitkomplexität?

Zeitkomplexität: Misst, wie die Laufzeit mit der Eingabegröße wächst
Beantwortet: „Was passiert, wenn meine Daten 10× größer werden?"
Betrachtet nicht die absolute Zeit

Big-O-Notation

Mathematische Notation zur Beschreibung des Worst-Case.

Einige gängige Komplexitätsklassen:

O(1): Konstante Zeit – größenunabhängig

O(1) verstehen

Ein Beispiel für eine O(1)-Operation ist ArrayList-get()

Interne (vereinfachte) Implementierung für eine ArrayList, die Strings hält:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Big-O-Notation

Mathematische Notation zur Beschreibung des Worst-Case

Einige gängige Komplexitätsklassen:

O(1): Konstante Zeit – größenunabhängig
O(n): Lineare Zeit – wächst mit der Eingabegröße

O(n) verstehen

Ein ähnliches Beispiel, aber für ArrayList-contains()

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Big-O-Notation

Mathematische Notation zur Beschreibung des Worst-Case

Einige gängige Komplexitätsklassen:

O(1): Konstante Zeit – größenunabhängig
O(n): Lineare Zeit – wächst mit der Eingabegröße
O(n²): Quadratische Zeit – wächst quadratisch mit der Eingabegröße

Ein Praxisbeispiel mit quadratischer Komplexität

// Finden eines Zahlenpaars mit gegebener Zielsumme
// Zeitkomplexität: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

Warum Zeitkomplexität zählt

Auswirkung der Eingabegröße:

O(1): 1.000 -> 1.000.000 Elemente = gleiche Zeit!
O(n): 1.000 -> 1.000.000 Elemente = 1.000× langsamer
O(n²): 1.000 -> 1.000.000 Elemente = 1.000.000× langsamer

Screenshot 2025-05-10 at 2.27.06 PM.png

Lass uns üben!

Codeoptimierung in Java