Big-O-notatie: ruimtecomplexiteit

Code optimaliseren in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Wat is ruimtecomplexiteit?

Tijdcomplexiteit beschrijft hoe inputgrootte de looptijd beïnvloedt
Ruimtecomplexiteit beschrijft hoe inputgrootte het geheugenverbruik beïnvloedt

Ruimtecomplexiteit begrijpen is cruciaal om apps te bouwen die:

Alleen de juiste hoeveelheid geheugen gebruiken, niet meer
Crashes zoals OutOfMemoryError vermijden

Big-O-notatie

Notatie is identiek aan tijdcomplexiteit.

Enkele veelvoorkomende klassen:

O(1): Constante tijd — onafhankelijk van grootte
O(n): Lineaire tijd — groeit met inputgrootte
O(n²): Kwadratische tijd — groeit kwadratisch met inputgrootte

Een maximumzoekmethode

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

Of onze integerarray 10 of 10 miljoen elementen heeft, we gebruiken maar geheugen voor één variabele: max
De ruimtecomplexiteit is O(1), oftewel constante ruimte

Een verdubbelmethode

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;
}

Heeft de input n elementen, dan is er ruimte nodig voor n extra elementen
De ruimtecomplexiteit is O(n) omdat het extra geheugen lineair met de inputgrootte groeit

Een vermenigvuldigingstabel-methode

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;
}

Is n 10, dan zijn 100 cellen nodig; is n 100, dan 10.000 cellen
Dit classificeren we als O(n²)

Waarom is ruimtecomplexiteit belangrijk?

Geheugen is eindig!

Onze eerdere voorbeelden bij een inputgrootte van 10.000 elementen:

findMax, O(1) -> slechts enkele extra bytes
doubleValues, O(n) -> ca. 40 KB extra geheugen
multiplicationTable, O(n²) -> ca. 400 MB extra geheugen

Staafdiagram met 8 byte extra voor findMax, 40 KB voor doubleValues en 400 MB voor multiplicationTable

Ruimtecomplexiteit vs. tijdcomplexiteit

Vergeet niet:

Soms ruilen we ruimte voor tijd
Soms ruilen we tijd voor ruimte
De juiste keuze hangt af van je specifieke beperkingen

Grafiek die de afruil tussen tijd en ruimte symboliseert

Laten we oefenen!

Code optimaliseren in Java