Премиум

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

Базовый Algorithms
≈ 2 мин чтения

Алгоритм тратит не только время

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

Если алгоритму нужны только несколько переменных независимо от длины массива, дополнительная память остаётся постоянной: 

int max = numbers[0];

for (int value : numbers) {
    if (value > max) {
        max = value;
    }
}

Переменная max занимает фиксированный объём памяти, поэтому дополнительная пространственная сложность такого решения — O(1).

Новая структура размером с вход

Если решение создаёт новый массив, размер которого зависит от n, память растёт вместе с входом. 

int[] doubled = new int[numbers.length];

for (int i = 0; i < numbers.length; i++) {
    doubled[i] = numbers[i] * 2;
}

Для n исходных элементов создаётся ещё n значений, поэтому дополнительная память имеет порядок O(n).

Память стека тоже учитывается

Дополнительная память — это не только массивы, коллекции и объекты, которые явно создаются через new. Каждый активный вызов метода хранит данные своего вызова в стеке. Поэтому глубокая рекурсия тоже может увеличивать пространственную сложность, даже если внутри метода не создаются большие структуры данных.

При анализе полезно задать простой вопрос: если вход станет в десять раз больше, понадобится ли алгоритму примерно столько же дополнительной памяти, в десять раз больше или объём почти не изменится?

Уточняй, что именно оцениваешь. Полная память включает и входные данные, а дополнительная пространственная сложность — только память, которую алгоритм использует сверх входа. В задачах чаще сравнивают именно второй вариант.
Назад Далее