Нотація Big-O: просторова складність

Оптимізація коду в Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Що таке просторова складність?

Часова складність описує, як розмір вхідних даних впливає на час виконання
Просторова складність описує, як розмір входу впливає на використання пам'яті

Розуміння просторової складності важливе, щоб створювати застосунки, які:

Використовують рівно стільки пам'яті, скільки потрібно
Уникають збоїв на кшталт OutOfMemoryError

Нотація Big-O

Нотація ідентична часовій складності.

Поширені класи складності:

O(1): Константна — не залежить від розміру
O(n): Лінійна — зростає з розміром входу
O(n²): Квадратична — зростає квадратично з розміром входу

Метод пошуку максимуму

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

Хай у масиві 10 елементів чи 10 мільйонів — ми все одно використовуємо пам'ять лише для однієї змінної max
Просторова складність — O(1), тобто константний простір

Метод подвоєння значень

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

Якщо вхід має n елементів, потрібен простір для ще n елементів
Просторова складність — O(n), бо додаткова пам'ять зростає лінійно з розміром входу

Метод побудови таблиці множення

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

Якщо n дорівнює 10, потрібно 100 комірок; якщо n дорівнює 100 — потрібно 10 000 комірок
Це класифікуємо як O(n²)

Чому просторова складність важлива?

Пам'ять — обмежений ресурс!

Наші попередні приклади при розмірі входу 10 000 елементів:

findMax, O(1) -> лише кілька байтів додатково
doubleValues, O(n) -> близько 40 KB додаткової пам'яті
multiplicationTable, O(n²) -> близько 400 MB додаткової пам'яті

Стовпчикова діаграма: +8 байтів для findMax, 40KB для doubleValues і 400MB для multiplicationTable

Просторова vs часова складність

Не забувайте:

Іноді ми обмінюємо простір на час
Іноді обмінюємо час на простір
Правильний вибір залежить від ваших обмежень

Графіка, що символізує компроміс між часом і простором

Давайте потренуємось!

Оптимізація коду в Java