Что такое space complexity

Space complexity — это big-O для памяти, которую алгоритм использует дополнительно к самому входу. То есть если функция получает на вход list из n элементов — эти n не входят в её space complexity, они уже выделены до вызова.

Учитывается то, что функция выделяет сама:

• Новые списки, словари, множества.
• Локальные переменные (но обычно константа).
• Стек рекурсии (важно).
• Внутренние буферы алгоритма.

Примеры классов памяти

O(1) — константная память

Функция использует только несколько переменных, независимо от n:

def total(lst):
    s = 0          # O(1)
    for x in lst:
        s += x     # переменная одна, не накапливается
    return s

Time O(n), space O(1). Это самый дешёвый класс памяти.

O(n) — линейная память

Функция создаёт новую коллекцию пропорционально входу:

def double_each(lst):
    return [x * 2 for x in lst]  # новый список из n элементов

Time O(n), space O(n). Часто встречается у функций «трансформируй вход и верни новый».

O(n) от рекурсии

Скрытый случай — рекурсия. Стек тоже занимает память:

def sum_recursive(lst, i=0):
    if i == len(lst):
        return 0
    return lst[i] + sum_recursive(lst, i + 1)

Time O(n), space O(n) — потому что глубина рекурсии n, каждый вызов кладёт стек-frame.

O(log n) — логарифмическая память

Появляется в рекурсиях с делением пополам (binary search recursive, merge sort стек):

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])    # O(log n) рекурсивная глубина
    right = merge_sort(lst[mid:])
    return merge(left, right)

Глубина рекурсии — log n (делим пополам). Так что стек O(log n). Правда, сам merge sort нелогично O(log n) по памяти — копии массивов добавляют O(n). Об этом ниже.

In-place vs not in-place

In-place алгоритм — тот, что использует только O(1) или O(log n) дополнительной памяти. Меняет вход «на месте», не выделяя новый массив того же размера.

Сравнение:

# In-place reverse, space O(1)
def reverse_in_place(lst):
    n = len(lst)
    for i in range(n // 2):
        lst[i], lst[n-1-i] = lst[n-1-i], lst[i]
    return lst

# Not in-place, space O(n)
def reverse_copy(lst):
    return lst[::-1]   # создаёт новый список из n элементов

Time у обоих O(n). Space: первый O(1), второй O(n).

Когда это важно для DE: если у вас в памяти 10GB данных и нужно их отсортировать — lst.sort() (in-place) против sorted(lst) (создаёт копию). Первая работает в 1x памяти, вторая в 2x. На большом наборе разница между «работает» и «MemoryError».

# In-place
lst.sort()         # O(n log n) time, O(log n) space (Timsort стек)

# Not in-place
new = sorted(lst)  # O(n log n) time, O(n) space (новый список + Timsort стек)

Измерения памяти: sys.getsizeof и его подвох

В Python есть sys.getsizeof(obj) — возвращает размер объекта в байтах. Но только самого объекта, без referenced. Это часто запутывает:

import sys

empty_list = []
lst_with_items = [1, 2, 3]
lst_big = list(range(100))

print(sys.getsizeof(empty_list))    # 56 (на 64-битной)
print(sys.getsizeof(lst_with_items)) # 88
print(sys.getsizeof(lst_big))       # 920

Вот подвох — у списка [1, 2, 3] getsizeof возвращает 88. Но в эти 88 байт не включён размер чисел 1, 2, 3. Они лежат как ссылки на отдельные int-объекты в памяти. Каждый int в Python — это объект ~28 байт.

import sys

a = [1, 2, 3]
print("Size of list:", sys.getsizeof(a))     # 88
print("Size of int:", sys.getsizeof(1))      # 28
print("Total real:", sys.getsizeof(a) + 3 * sys.getsizeof(1))  # 88 + 84 = 172

Для рекурсивного измерения нужен другой инструмент.

pympler.asizeof — рекурсивный размер

# pip install pympler
from pympler import asizeof

a = [1, 2, 3]
print(asizeof.asizeof(a))   # ~120-150, реальный размер со всеми ссылками

big = list(range(10000))
print(sys.getsizeof(big))   # ~83000 (только массив указателей)
print(asizeof.asizeof(big)) # ~360000 (массив + все int-ы)

Разница в 4 раза — потому что getsizeof не считает int-ы, а они в 4 раза больше списка указателей.

tracemalloc — пиковая память за период

tracemalloc (stdlib) измеряет память, выделенную Python между snapshot-ами. Идеален для бенчмарков:

import tracemalloc

def make_big_list(n):
    return [x ** 2 for x in range(n)]

tracemalloc.start()
big = make_big_list(100_000)
current, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()

print(f"Current: {current / 1024 / 1024:.2f} MB")
print(f"Peak:    {peak / 1024 / 1024:.2f} MB")

Типичный вывод:

Current: 3.85 MB
Peak:    3.85 MB

Это самый удобный инструмент для измерения «сколько памяти жрёт мой алгоритм». Им мы будем пользоваться на протяжении всего курса.

Попробуй сам: измеряем dedupe-варианты

import tracemalloc

def dedupe_list(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

def dedupe_set(items):
    return list(set(items))

data = list(range(100_000)) * 2

# Замер 1: list-based
tracemalloc.start()
res1 = dedupe_list(data)
_, peak1 = tracemalloc.get_traced_memory()
tracemalloc.stop()

# Замер 2: set-based
tracemalloc.start()
res2 = dedupe_set(data)
_, peak2 = tracemalloc.get_traced_memory()
tracemalloc.stop()

print(f"dedupe_list peak: {peak1 / 1024:.0f} KB")
print(f"dedupe_set  peak: {peak2 / 1024:.0f} KB")

dedupe_list peak:   800 KB
dedupe_set  peak:  6500 KB

Space-time tradeoff

Часто можно обменять память на скорость или наоборот. Примеры:

• Memoization (dict-кэш) — добавляет O(n) памяти, чтобы избежать пересчёта. Превращает O(2^n) Фибоначчи в O(n).
• Hash-based dedup (set) — O(n) памяти, но O(n) time. List-based — O(1) памяти, но O(n²) time.
• Inverted index — для текстового поиска: O(N) памяти, но O(log) поиск вместо O(N).

Обратное тоже верно:

• Streaming — обрабатывать данные потоком, не загружая в память целиком. Жертвуем удобством случайного доступа, но получаем O(1) памяти на запись.
• In-place sort — O(1) дополнительной памяти, но обычно медленнее out-of-place (нет prefetcher-friendly доступа).

В data engineering это решение приходится принимать постоянно. У вас 100GB JSON-ов и 16GB RAM — никакого data.json.read().parse() целиком, только streaming. У вас 1M событий и нужна агрегация — set в памяти ок, но всегда оценивайте пиковое потребление.

Шпаргалка по space complexity

В следующем уроке — амортизированный анализ. Что такое «O(1) amortized», почему list.append имеет такую сложность и как это работает.