Notația Big-O: complexitatea spațială

Optimizarea codului în Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Ce este complexitatea spațială?

Complexitatea temporală descrie cum afectează dimensiunea intrării timpul de execuție
Complexitatea spațială descrie cum afectează dimensiunea intrării utilizarea memoriei

Înțelegerea complexității spațiale este esențială pentru aplicații care:

Utilizează exact memoria necesară, fără surplus
Evită erori de tipul OutOfMemoryError

Notația Big-O

Notația este identică cu cea pentru complexitatea temporală.

Clase de complexitate frecvente:

O(1): Timp constant - independent de dimensiunea intrării
O(n): Timp liniar - crește odată cu dimensiunea intrării
O(n²): Timp pătratic - crește pătratic cu dimensiunea intrării

O metodă de găsire a maximului

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

Indiferent dacă tabloul are 10 sau 10 milioane de elemente, folosim memorie doar pentru o singură variabilă, max
Complexitatea spațială este O(1) sau spațiu constant

O metodă de dublare

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

Dacă intrarea are n elemente, avem nevoie de spațiu pentru încă n elemente
Complexitatea spațială este O(n), deoarece memoria suplimentară crește liniar cu dimensiunea intrării

O metodă pentru tabela înmulțirii

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

Dacă n este 10, avem nevoie de 100 de celule; dacă n este 100, avem nevoie de 10.000
Clasificăm aceasta drept O(n²)

De ce este importantă complexitatea spațială?

Memoria este o resursă limitată!

Exemplele anterioare, pentru o dimensiune de intrare de 10.000 de elemente:

findMax, O(1) -> câțiva octeți suplimentari
doubleValues, O(n) -> aproximativ 40 KB memorie suplimentară
multiplicationTable, O(n²) -> aproximativ 400 MB memorie suplimentară

Diagramă cu bare care arată o creștere de 8 octeți pentru findMax, 40 KB pentru doubleValues și 400 MB pentru multiplicationTable

Complexitatea spațială vs. temporală

De reținut:

Uneori sacrificăm spațiul pentru timp
Uneori sacrificăm timpul pentru spațiu
Alegerea corectă depinde de constrângerile specifice

Grafică ce simbolizează compromisul dintre timp și spațiu

Să exersăm!

Optimizarea codului în Java