Нотация «О большое»: пространственная сложность

Оптимизация кода на Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Что такое пространственная сложность?

Временна́я сложность описывает, как размер входных данных влияет на время выполнения
Пространственная сложность описывает, как размер входных данных влияет на использование памяти

Понимание пространственной сложности важно для приложений, которые:

Используют ровно столько памяти, сколько нужно
Не аварийно завершаются с ошибками вроде OutOfMemoryError

Нотация «О большое»

Нотация идентична нотации временно́й сложности.

Распространённые классы сложности:

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 КБ дополнительной памяти
multiplicationTable, O(n²) -> около 400 МБ дополнительной памяти

Столбчатая диаграмма: прирост памяти для findMax — 8 байт, для doubleValues — 40 КБ, для multiplicationTable — 400 МБ

Пространственная сложность и временна́я сложность

Важно помнить:

Иногда мы жертвуем памятью ради скорости
Иногда — скоростью ради памяти
Правильный выбор зависит от конкретных ограничений задачи

Иллюстрация компромисса между временем и памятью

Давайте потренируемся!

Оптимизация кода на Java