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

При анализе алгоритма важно учитывать не только время его работы. Во время выполнения программе также нужна память: для переменных, новых массивов, таблиц и других промежуточных данных.

То, как растёт объём необходимой памяти при увеличении входных данных, называют пространственной сложностью. Как и временную сложность, её описывают с помощью Big O.

Время и память – разные характеристики

Посмотрим на знакомый алгоритм поиска максимума:

findMaxпсевдокод
function findMax(numbers):    max = numbers[0]    for number in numbers:        if number > max:            max = number    return max

В худшем случае он проходит по всем n элементам:

Но во время работы алгоритм хранит только несколько дополнительных значений – например max и текущий number. Их количество не зависит от размера массива:

Поэтому один и тот же алгоритм может иметь разные оценки времени и памяти:

РесурсСложность
ВремяO(n)
ПамятьO(1)

Что считается дополнительной памятью

У алгоритма уже есть входные данные. Например, findMax получает массив:

numbers = [4, 7, 2, 9, 5]

Этот массив существовал ещё до запуска функции. Во время работы алгоритм дополнительно хранит только несколько значений:

maxnumber

Поэтому полезно разделять:

  • входные данные – то, что алгоритм получил;
  • дополнительную память – то, что он создаёт или хранит во время работы.

Для findMax размер массива может расти:

а количество дополнительной памяти остаётся примерно тем же. Поэтому:

O(1) памяти

Рассмотрим простой алгоритм обмена двух элементов:

swapFirstLastпсевдокод
function swapFirstLast(numbers):    temp = numbers[0]    numbers[0] = numbers[numbers.length - 1]    numbers[numbers.length - 1] = temp

Для массива из пяти элементов нужна переменная temp. Для массива из миллиона элементов – всё та же одна переменная. Количество дополнительной памяти не зависит от n, поэтому это O(1).

Как и со временем, O(1) не означает «одна ячейка памяти». Например, поиск в отсортированном массиве держит три дополнительных значения:

searchпсевдокод
function search(numbers, target):    left = 0    right = numbers.length - 1    while left <= right:        mid = (left + right) // 2        ...

Массив может быть любого размера, а дополнительных значений всё равно три: left, right и mid. Их количество не растёт вместе с входом, поэтому пространственная сложность по-прежнему O(1).

Когда появляется O(n)

Теперь рассмотрим другой алгоритм. Нужно создать новый массив, содержащий удвоенные значения:

doubleNumbersпсевдокод
function doubleNumbers(numbers):    result = []    for number in numbers:        result.push(number * 2)    return result

Посмотрим, как result заполняется для входа [2, 5, 8, 4]:

Новый массив растёт вместе с входом
function doubleNumbers(numbers):
result = []
for number in numbers:
result.push(number * 2)
return result
Запускаем doubleNumbers для 4 элементов.
doubleNumbers([2, 5, 8, 4])
2584numbersresult
Значений в памяти0

Новый массив содержит примерно столько же элементов, сколько исходный. Если n = 10, в result будет около 10 элементов. Если n = 1 000 – около 1 000.

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

Изменить данные или создать новые

Задача: увеличить каждый элемент массива в два раза. Можно создать новый массив – тогда дополнительная память O(n). Но можно изменить исходный:

doubleNumbersпсевдокод
function doubleNumbers(numbers):    for i = 0; i < numbers.length; i += 1:        numbers[i] *= 2    return numbers

Теперь дополнительный массив не создаётся: мы изменяем элементы прямо там, где они уже находятся. Дополнительная память – O(1). Такой способ работы называют in-place: алгоритм изменяет данные на месте и не создаёт дополнительную структуру сравнимого размера.

Оба варианта дают одинаковые значения, но используют память по-разному

Но in-place не всегда лучше

Может показаться, что вариант с O(1) памяти всегда предпочтительнее. Но у него есть цена: исходные данные изменяются. Был массив numbers = [2, 5, 8], после in-place алгоритма в нём [4, 10, 16] – первоначальных значений больше нет.

Иногда именно это нам и нужно. Но иногда оригинальные данные должны сохраниться – тогда создание нового массива result = [4, 10, 16] может быть правильным решением, даже если оно использует больше памяти.

Поэтому меньшая пространственная сложность не означает автоматически «лучший алгоритм». Всё зависит от требований задачи.

O(n²) памяти тоже возможно

Дополнительная структура не обязательно должна быть одномерным массивом. Допустим, для каждого из n элементов мы храним информацию о его связи с каждым другим элементом. При трёх элементах получится таблица 3 × 3, при десяти – 10 × 10, при тысяче – 1 000 × 1 000.

Элементов в два раза больше – ячеек примерно в четыре раза больше

Количество ячеек растёт примерно как n * n, то есть это O(n²) памяти.

Не вся дополнительная память видна как массив

Иногда алгоритм не создаёт явных массивов или объектов, но всё равно использует дополнительную память. Посмотрим на функцию, которая вызывает саму себя:

countdownпсевдокод
function countdown(n):    print(n)    if n == 0:        return    countdown(n - 1)

Каждый незавершённый вызов функции должен где-то храниться. Для этого программа использует стек вызовов:

Что происходит в стеке вызовов
function countdown(n):
print(n)
if n == 0:
return
countdown(n - 1)
countdown(2)
Запускаем countdown(2). Вызов ещё не завершён, поэтому он лежит в стеке.
Консоль
Нет вывода в консоль.

Вызовы функций тоже занимают память. Если глубина вложенных вызовов растёт вместе с n, память тоже может иметь сложность O(n) – даже если алгоритм не создал ни одного массива.

Пространственная сложность и входные данные

Здесь есть нюанс в терминологии. Иногда под пространственной сложностью считают всю память, необходимую алгоритму, включая сами входные данные – тогда массив из n элементов уже занимает O(n) памяти.

Но очень часто при сравнении алгоритмов отдельно рассматривают auxiliary space – дополнительную память, которую алгоритм создаёт сверх входа. Вернёмся к findMax:

findMaxпсевдокод
function findMax(numbers):    max = numbers[0]    for number in numbers:        if number > max:            max = number    return max

Сам массив numbers занимает O(n) – это вход. А дополнительно алгоритм хранит только max и number, поэтому его дополнительная память – O(1).

В этом курсе, если не сказано иначе, говоря о памяти алгоритма, мы будем иметь в виду именно дополнительную память: так сравнивать решения удобнее.

Время и память могут обмениваться друг на друга

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

Без дополнительной структуры можно каждый раз снова искать его среди предыдущих элементов. Но можно сохранять просмотренные значения:

seenпсевдокод
seen = Set()for value in numbers:    if value in seen:        ...    seen.add(value)

Теперь мы используем дополнительную структуру seen. В худшем случае в ней может накопиться примерно n значений – это O(n) памяти. Зато такая структура позволяет выполнять нужные проверки значительно быстрее.

Эта идея называется компромиссом между временем и памятью, или time-space tradeoff. Иногда мы экономим память ценой дополнительных вычислений, иногда наоборот – используем больше памяти, чтобы сократить время работы.

Это не строгое правило, а распространённый компромисс

Как анализировать память по коду

На первых этапах можно использовать несколько простых ориентиров. Несколько переменных с простыми значениями – числами, строками, логическими – обычно O(1):

left = 0right = numbers.length - 1result = 0

Новый массив размером примерно n – обычно O(n):

result = []for value in numbers:    result.push(value)

Таблица размером n × n – обычно O(n²). А рекурсия глубиной около n может потребовать O(n) памяти в стеке вызовов:

function process(n):    if n == 0:        return    process(n - 1)

Как и со временем, в реальных алгоритмах ситуации бывают сложнее. Но пока важно научиться замечать, какие дополнительные данные растут вместе с размером входа.

Сравниваем алгоритм сразу по двум характеристикам

Теперь алгоритм можно описать не одной, а сразу двумя оценками:

АлгоритмВремяПамять
Поиск максимумаO(n)O(1)
Копия массиваO(n)O(n)
Таблица всех парO(n²)O(n²)
copyпсевдокод
function copy(numbers):    result = []    for number in numbers:        result.push(number)    return result

Эти значения не обязаны совпадать: алгоритм вполне может иметь время O(n²) и память O(1). Временная и пространственная сложность анализируются отдельно.

Что важнее – время или память

Универсального ответа нет. Для одной программы критична скорость, для другой доступно очень мало памяти. В мобильном устройстве, встроенной системе или при работе с огромными объёмами данных память может быть серьёзным ограничением. В другом случае несколько дополнительных мегабайт могут быть совершенно неважны, если это заметно ускоряет работу.

Поэтому хороший алгоритм – это не обязательно алгоритм с минимальным O во всех характеристиках. Важно, чтобы его свойства соответствовали требованиям конкретной задачи.

// теперь вы знаете

  1. Пространственная сложность описывает, как растёт дополнительная память при увеличении n; память самих входных данных обычно не считают (auxiliary space)
  2. O(1) – несколько переменных; O(n) – структура размером со вход (копия, result, множество seen); O(n²) – таблица n × n
  3. In-place меняет данные на месте: память O(1), но исходные значения теряются
  4. Незавершённые вызовы функций лежат в стеке: глубина рекурсии около n – это O(n) памяти
  5. Время и память оцениваются отдельно: у алгоритма может быть время O(n²) и память O(1)
  6. Дополнительная память может сокращать работу – это компромисс между временем и памятью

Проверьте себя

Алгоритм проходит по массиву и хранит только одну дополнительную переменную. Какова его дополнительная пространственная сложность?

function findMax(numbers):
    max = numbers[0]
    for number in numbers:
        if number > max:
            max = number
    return max

Алгоритм создаёт новый массив и добавляет в него по одному значению для каждого элемента входа. Какова дополнительная пространственная сложность?

function copy(numbers):
    result = []
    for number in numbers:
        result.push(number)
    return result

Какой из двух вариантов использует меньше дополнительной памяти?

# вариант A
function doubleNumbers(numbers):
    result = []
    for number in numbers:
        result.push(number * 2)
    return result
# вариант B
function doubleNumbers(numbers):
    for i = 0; i < numbers.length; i += 1:
        numbers[i] *= 2
    return numbers

Дополнительная пространственная сложность алгоритма – O(1). Означает ли это, что входные данные тоже обязательно занимают O(1) памяти?

У алгоритма время O(n) и память O(n). Что из этого следует?

Выберите все правильные утверждения.

Выбери все верные варианты

Зачем алгоритм иногда намеренно использует дополнительную структуру размером O(n)?

Предыдущий урокBig OСледующий урок Как анализировать сложность кода