Big O для памяти
Big O может описывать память так же, как и время: сколько дополнительного места нужно алгоритму при росте входных данных?
Мы считаем только дополнительное место — переменные и списки, которые создаёт алгоритм, — а не сами входные данные. Это дополнительное место называется вспомогательной памятью.
O(1) по памяти: фиксированное количество переменных независимо от входных данных. O(n) по памяти: для каждого входного элемента сохраняется что-то новое, например копия или множество уже встреченных значений.
O(1) по памяти
Алгоритм, который хранит лишь несколько простых переменных, использует постоянную память. В списке может быть десять элементов или десять миллионов — у самого алгоритма по-прежнему есть только его счётчики.
Суммирование, поиск максимума и линейный поиск — все они работают за O(n) по времени, но O(1) по памяти: они читают много, а запоминают почти ничего.
Сумма с одной переменной
Весь алгоритм запоминает ровно одно число — total. Расход памяти не растёт вместе со списком: O(1) по памяти.
Вывод: полная программа на Python
nums = [3, 1, 4, 1, 5, 9, 2, 6]
# Одна дополнительная переменная, какой бы длины ни был список.
total = 0
for n in nums:
total += n
print("сумма:", total)
O(n) по памяти
Как только алгоритм строит что-то с одной записью на каждый входной элемент — новый список, словарь, — его пространственная сложность становится O(n): вдвое больше входных данных — вдвое больше памяти.
Само по себе это не плохо. Это просто цена, которую стоит замечать, потому что ею можно обменяться.
Построение нового списка
Выходной список получает по одному элементу на каждый входной элемент. 5 на входе, 5 на выходе — память растёт вместе с входными данными: O(n) по памяти.
Вывод: полная программа на Python
nums = [1, 2, 3, 4, 5]
# Новый список с одним элементом на каждый входной элемент.
doubled = []
for n in nums:
doubled.append(n * 2)
print("вход: ", nums)
print("выход:", doubled)
Обмен памяти на время
Часто можно потратить память, чтобы сэкономить время. Классический пример — Two Sum (сумма двух): найти в списке два числа, которые в сумме дают целевое значение.
Прямой способ проверяет каждую пару — O(n²) по времени, O(1) по памяти. Быстрый способ проходит по списку один раз и запоминает каждое встреченное число во множестве. Для каждого числа он спрашивает: «встречал ли я уже target - n?» — O(n) по времени, O(n) по памяти.
Обычно такой обмен того стоит: память в машину можно добавить, а время — нельзя.
Two Sum с двумя циклами
Проверяется каждая пара, пока не найдётся совпадение, — до 15 проверок для 6 элементов, и количество проверок растёт как квадрат размера входных данных. Дополнительная память не используется.
Вывод: полная программа на Python
nums = [2, 11, 15, 1, 8, 7]
target = 9
checks = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
checks += 1
if nums[i] + nums[j] == target:
print("найдено:", nums[i], "+", nums[j], "— проверок:", checks)
print("всего проверок:", checks)
Two Sum с множеством
Один проход, 6 проверок. Каждое число ищется и сохраняется во множестве seen — работа за постоянное время на каждый элемент. Множество — это та память O(n), которая покупает время O(n).
Вывод: полная программа на Python
nums = [2, 11, 15, 1, 8, 7]
target = 9
seen = set()
for n in nums:
if target - n in seen:
print("найдено:", target - n, "+", n)
seen.add(n)
print("проверено элементов:", len(nums), "(каждый один раз)")