Notace Big-O: prostorová složitost

Optimalizace kódu v Javě

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Co je prostorová složitost?

Časová složitost popisuje, jak velikost vstupu ovlivňuje dobu běhu
Prostorová složitost popisuje, jak velikost vstupu ovlivňuje využití paměti

Porozumění prostorové složitosti je klíčové pro vývoj aplikací, které:

Využívají pouze nezbytné množství paměti
Vyhýbají se chybám jako OutOfMemoryError

Notace Big-O

Notace je stejná jako u časové složitosti.

Některé běžné třídy složitosti:

O(1): Konstantní – nezávislá na velikosti vstupu
O(n): Lineární – roste s velikostí vstupu
O(n²): Kvadratická – roste kvadraticky s velikostí vstupu

Metoda pro nalezení maxima

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

Ať má naše pole 10 nebo 10 milionů prvků, využíváme paměť pouze pro jednu proměnnou, max
Prostorová složitost je O(1), tedy konstantní

Metoda pro zdvojení hodnot

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

Pokud má vstup n prvků, potřebujeme prostor pro n dalších prvků
Prostorová složitost je O(n), protože potřebná paměť roste lineárně s velikostí vstupu

Metoda pro sestavení násobilky

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

Pokud je n rovno 10, potřebujeme 100 buněk; pokud je n rovno 100, potřebujeme 10 000 buněk
Tuto složitost klasifikujeme jako O(n²)

Proč je prostorová složitost důležitá?

Paměť je omezený zdroj!

Naše předchozí příklady pro vstup o velikosti 10 000 prvků:

findMax, O(1) -> jen několik bajtů navíc
doubleValues, O(n) -> přibližně 40 KB navíc
multiplicationTable, O(n²) -> přibližně 400 MB navíc

Sloupcový graf zobrazující nárůst paměti o 8 bajtů pro findMax, 40 KB pro doubleValues a 400 MB pro multiplicationTable

Prostorová vs. časová složitost

Nezapomeňte:

Někdy vyměníme prostor za čas
Někdy vyměníme čas za prostor
Správná volba závisí na konkrétních omezeních

Grafika symbolizující kompromis mezi časem a prostorem

Pojďme si procvičit!

Optimalizace kódu v Javě