Notacja Big-O: złożoność pamięciowa

Optymalizacja kodu w Javie

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Czym jest złożoność pamięciowa?

Złożoność czasowa opisuje wpływ rozmiaru danych na czas wykonania
Złożoność pamięciowa opisuje wpływ rozmiaru danych na zużycie pamięci

Zrozumienie złożoności pamięciowej jest kluczowe przy budowaniu aplikacji, które:

Używają tylko niezbędnej ilości pamięci
Unikają awarii z błędami takimi jak OutOfMemoryError

Notacja Big-O

Notacja jest identyczna jak w przypadku złożoności czasowej.

Najczęstsze klasy złożoności:

O(1): Stała – niezależna od rozmiaru danych
O(n): Liniowa – rośnie wraz z rozmiarem danych
O(n²): Kwadratowa – rośnie kwadratowo względem rozmiaru danych

Metoda znajdowania maksimum

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

Niezależnie od tego, czy tablica ma 10 czy 10 milionów elementów, używamy pamięci tylko dla jednej zmiennej: max
Złożoność pamięciowa wynosi O(1), czyli jest stała

Metoda podwajania wartości

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

Jeśli dane wejściowe mają n elementów, potrzebujemy miejsca na n dodatkowych elementów
Złożoność pamięciowa wynosi O(n), ponieważ zużycie pamięci rośnie liniowo

Metoda tabliczki mnożenia

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

Jeśli n wynosi 10, potrzebujemy 100 komórek; jeśli n wynosi 100, potrzebujemy 10 000 komórek
Klasyfikujemy to jako O(n²)

Dlaczego złożoność pamięciowa jest ważna?

Pamięć jest zasobem skończonym!

Nasze wcześniejsze przykłady dla danych wejściowych o rozmiarze 10 000 elementów:

findMax, O(1) -> zaledwie kilka dodatkowych bajtów
doubleValues, O(n) -> około 40 KB dodatkowej pamięci
multiplicationTable, O(n²) -> około 400 MB dodatkowej pamięci

Wykres słupkowy pokazujący wzrost zużycia pamięci: 8 bajtów dla findMax, 40 KB dla doubleValues i 400 MB dla multiplicationTable

Złożoność pamięciowa a czasowa

Pamiętaj:

Czasem wymieniamy pamięć na czas
Czasem wymieniamy czas na pamięć
Właściwy wybór zależy od konkretnych ograniczeń

Grafika symbolizująca kompromis między czasem a pamięcią

Czas na ćwiczenia!

Optymalizacja kodu w Javie