Big-O-Notation: Speicherkomplexität

Codeoptimierung in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Was ist Speicherkomplexität?

Die Zeitkomplexität beschreibt, wie die Eingabegröße die Laufzeit beeinflusst
Die Speicherkomplexität beschreibt, wie die Eingabegröße den Speicherverbrauch beeinflusst

Die Speicherkomplexität zu verstehen, ist entscheidend, um Anwendungen zu bauen, die:

nur so viel Speicher nutzen wie nötig
Abstürze mit Fehlern wie OutOfMemoryError vermeiden

Big-O-Notation

Die Notation ist identisch zur Zeitkomplexität.

Einige gängige Komplexitätsklassen:

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

Eine Methode zum Finden des Maximums

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Ob unser Integer-Array 10 Elemente hat oder 10 Millionen: Wir brauchen nur Speicher für eine einzige Variable, max
Die Speicherkomplexität ist O(1) bzw. konstant

Eine Verdopplungsmethode

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

Hat die Eingabe n Elemente, brauchen wir Platz für n zusätzliche Elemente
Die Speicherkomplexität ist O(n), da der Zusatzspeicher linear mit der Eingabegröße wächst

Eine Methode für die Einmaleins-Tabelle

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

Ist n gleich 10, brauchen wir 100 Zellen; ist n 100, brauchen wir 10.000 Zellen
Wir klassifizieren das als O(n²)

Warum ist Speicherkomplexität wichtig?

Speicher ist eine endliche Ressource!

Unsere vorherigen Beispiele in Aktion für eine Eingabegröße von 10.000 Elementen:

findMax, O(1) -> nur ein paar zusätzliche Bytes
doubleValues, O(n) -> ca. 40 KB Zusatzspeicher
multiplicationTable, O(n²) -> ca. 400 MB Zusatzspeicher

Balkendiagramm mit 8 Byte Mehrverbrauch für findMax, 40 KB für doubleValues und 400 MB für multiplicationTable

Speicher- vs. Zeitkomplexität

Nicht vergessen:

Manchmal tauschen wir Speicher gegen Zeit
Manchmal tauschen wir Zeit gegen Speicher
Die richtige Wahl hängt von deinen konkreten Rahmenbedingungen ab

Grafik, die den Trade-off zwischen Zeit und Speicher symbolisiert

Lass uns üben!

Codeoptimierung in Java