Big-O-notation: minneskomplexitet

Optimera kod i Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Vad är minneskomplexitet?

Tidskomplexitet beskriver hur indata-storlek påverkar körtiden
Minneskomplexitet beskriver hur indata-storlek påverkar minnesanvändningen

Att förstå minneskomplexitet är viktigt för att bygga applikationer som:

Bara använder det minne som behövs
Undviker krascher med fel som OutOfMemoryError

Big-O-notation

Notationen är identisk med tidskomplexitet.

Vanliga komplexitetsklasser:

O(1): Konstant tid – oberoende av storleken
O(n): Linjär tid – växer med indata-storleken
O(n²): Kvadratisk tid – växer kvadratiskt med indata-storleken

En metod för att hitta maxvärdet

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

Oavsett om heltalsarrayen har 10 eller 10 miljoner element använder vi bara minne för en enda variabel, max
Minneskomplexiteten är O(1), det vill säga konstant minnesåtgång

En fördubblingsmetod

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

Om indata har n element behöver vi plats för n ytterligare element
Minneskomplexiteten är O(n) eftersom det extra minnesbehovet växer linjärt med indata-storleken

En metod för multiplikationstabell

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

Om n är 10 behöver vi 100 celler; om n är 100 behöver vi 10 000 celler
Vi klassificerar detta som O(n²)

Varför är minneskomplexitet viktigt?

Minne är en begränsad resurs!

Våra tidigare exempel i praktiken, för en indata-storlek på 10 000 element:

findMax, O(1) -> bara några extra byte
doubleValues, O(n) -> ungefär 40 KB extra minne
multiplicationTable, O(n²) -> ungefär 400 MB extra minne

Stapeldiagram som visar 8 bytes minnesökning för findMax, 40 KB för doubleValues och 400 MB för multiplicationTable

Minneskomplexitet vs. tidskomplexitet

Kom ihåg:

Ibland byter vi minne mot tid
Ibland byter vi tid mot minne
Rätt val beror på dina specifika förutsättningar

Grafik som symboliserar avvägningen mellan tid och minne

Nu kör vi en övning!

Optimera kod i Java