Алгоритмы

Пространственная сложность: память тоже стоит денег

Цели урока

  • Понять разницу между time и space complexity
  • Освоить анализ auxiliary vs total space
  • Учитывать память стека при рекурсии
  • Применять space-time tradeoff осознанно

Предварительные знания

  • Big O нотация
  • Big O: Язык эффективности

KV-cache у GPT-4 при 128K контексте занимает больше 10 GB RAM на один запрос. Это не баг архитектуры - это осознанный space-time tradeoff: хранить attention keys/values дорого, но без этого каждый новый токен стоил бы O(n^2) пересчёта. Пространственная сложность здесь буквально определяет, существует ли продукт.

  • **OpenAI GPT-4** - KV-cache съедает гигабайты RAM на запрос, но делает streaming возможным
  • **Mobile apps** - 3-4 GB RAM на телефоне делят все процессы одновременно
  • **Embedded** - микроконтроллеры Arduino работают с 2KB RAM: каждый байт на счету
  • **Apache Kafka** - 64 GB RAM на брокер для хранения log-буферов в памяти
  • **Redis** - вся база данных в RAM: O(n) памяти это бизнес-модель, а не ограничение

Donald Knuth и первый анализ памяти

В 1968 году Knuth опубликовал первый том 'The Art of Computer Programming', где впервые систематически описал как анализировать space complexity алгоритмов - тогда это называлось 'storage complexity'. В 1960-е годы компьютеры имели 16-64 KB RAM, и анализ памяти был вопросом выживания программы. Именно Knuth ввёл Big O в системный обиход программистов и показал, что пространственный анализ неотделим от временного.

Почему память важна?

**OpenAI в 2023 году тратил около 700 000 долларов в день** на инфраструктуру ChatGPT. Основная статья расходов - не GPU-время. RAM. Каждый активный контекст пользователя занимает память пропорционально длине разговора. Умножь на миллионы параллельных сессий - и получишь почему пространственная сложность влияет на P&L компании.

Алгоритм может быть молниеносным по времени и при этом убивать продакшн через OOM. **Google** в своё время отклонил индексирующий алгоритм, который давал 10x ускорение, - он требовал 500 GB RAM на сервер вместо 50 GB. Ускорение не стоило 10x затрат на железо.

РесурсСтоимостьСкорость доступа
CPU регистрывстроено в чипменее 1 нс
L1/L2 Cacheоколо 100 USD/MB1-5 нс
RAM (DDR5)около 5 USD/GB~100 нс
NVMe SSDоколо 0.1 USD/GB~100 мкс
HDDоколо 0.02 USD/GB~10 мс

**Память - это всегда trade-off.** Быстрее по времени? Значит, скорее всего, больше памяти. Экономим память? Значит, больше вычислений. Нет бесплатных обедов.

Алгоритм A работает за O(n) с O(n²) памяти. Алгоритм B за O(n²) с O(1) памяти. При n = 1 000 000 какой выбрать для сервера с 1GB RAM?

O-нотация для памяти

**Space complexity** записывается той же Big O нотацией, что и временная. Только считается не количество операций, а количество ячеек памяти в зависимости от размера входа n.

**S(n)** - сколько дополнительной памяти нужно алгоритму при входе размера n. Асимптотически, без констант.

Функция создаёт словарь {элемент: индекс} для массива длиной n. Space complexity?

Auxiliary vs Total Space

Критическое различие, которое путают даже опытные инженеры. **Total space** - вся память процесса: входные данные + выход + вспомогательная. **Auxiliary space** - только дополнительная память, которую алгоритм создаёт сам, не считая вход.

На практике обычно говорят об **auxiliary space** - именно она под контролем разработчика. Входные данные даны системой, с ними ничего не сделать.

**In-place алгоритм** - тот, который использует O(1) auxiliary space. Модифицирует вход напрямую, не создавая копий. В ML: gradient checkpointing делает forward pass in-place, пересчитывая активации на backward - O(sqrt(n)) memory вместо O(n).

АлгоритмTotal SpaceAuxiliary Space
Merge SortO(n)O(n) - временный массив слияния
Quick SortO(n)O(log n) - стек рекурсии
Heap SortO(n)O(1) - heap in-place
Counting SortO(n + k)O(k) - счётчики для диапазона

Почему in-place алгоритмы предпочтительнее при работе с большими данными?

Рекурсия: скрытая память стека

**Рекурсия - источник неочевидных утечек памяти.** Каждый вызов функции добавляет frame в call stack: локальные переменные, аргументы, адрес возврата. Глубина стека = дополнительная память. В Python по умолчанию лимит ~1000 вызовов. В Node.js - ~10000. Превышение - **Stack Overflow**.

**Tail call optimization (TCO)** - когда компилятор превращает рекурсию в цикл, O(n) stack превращается в O(1). Python намеренно не делает TCO - Guido van Rossum считает трассировку стека важнее экономии памяти. Scheme, Haskell, Scala - делают.

Рекурсивный бинарный поиск имеет space complexity:

Space-Time Tradeoff

**Фундаментальный закон:** память и время обмениваются. Потратить память - сэкономить время. Сэкономить память - потратить время. Этот принцип пронизывает всё: от hash table до трансформеров.

**Memoization** - классический пример tradeoff. Fibonacci с мемоизацией: O(2^n) → O(n) по времени ценой O(n) памяти. Именно так работает KV-cache в трансформерах: хранить attention keys/values - дорого по памяти, но инференс ускоряется в десятки раз.

ТехникаТратимПолучаем
Hash Table (dict/set)O(n) памятьO(1) lookup вместо O(n)
Memoization / DPO(n) памятьИзбавляемся от повторных вычислений
PrecomputationO(n) память + время на стартеO(1) ответы на запросы
Streaming (sketches)Точность ~1-5%O(1) память вместо O(n)
KV-cache (LLM)Гигабайты RAMИнференс без O(n^2) пересчёта attention

LRU Cache - это пример space-time tradeoff. Что жертвуется, что получается?

Практика: анализ реальных алгоритмов

Space complexity структур данных и алгоритмов - не теория, а ежедневный инструмент. **Graph (adjacency matrix)** жрёт O(V²) памяти даже для разреженных графов - поэтому социальные сети с миллиардом узлов используют adjacency lists (O(V + E)).

На собеседовании всегда называть обе сложности: time AND space. Инженер, который говорит только O(n) по времени - не видит половины картины.

Для embedded системы с 1KB RAM нужно найти медиану потока чисел. Какой подход?

Space Complexity

  • Space complexity - сколько памяти нужно алгоритму асимптотически
  • Auxiliary space - только дополнительная память, не считая входные данные
  • Рекурсия скрыто потребляет O(глубина) памяти на call stack
  • Space-time tradeoff: memoization, hash tables, KV-cache - везде одна идея
  • In-place алгоритмы используют O(1) auxiliary space - Heap Sort, Quick Sort
  • На embedded и при работе с петабайтами O(1) space - не опция, а требование

Связанные темы

Space complexity - фундамент для выбора алгоритмов сортировки и проектирования структур данных при ограниченной памяти.

  • Амортизированный анализ — Продвинутый анализ сложности с динамическими аллокациями
  • Сортировки O(n²) — In-place сортировки с O(1) auxiliary space
  • Merge Sort — Эталон O(n) auxiliary space - цена за стабильность

Вопросы для размышления

  • Ты проектируешь сервис потоковой обработки логов: 10 миллионов строк в секунду, каждая строка до 512 байт. Менеджер просит добавить фичу - найти топ-100 самых частых IP-адресов за последние 5 минут. Какие подходы рассмотришь? Где проходит граница между тем что можно держать в RAM и тем что нельзя - и как space-time tradeoff меняет дизайн решения?

Связанные уроки

  • alg-01-big-o — Time complexity - первая половина уравнения, space - вторая
  • alg-03-amortized — Амортизированный анализ покрывает динамические аллокации
  • alg-05-merge-sort — Merge Sort - классический пример O(n) auxiliary space
  • arch-08-memory-hierarchy — Физика памяти: почему cache locality ломает Big O
  • ml-09-gradient-descent — Gradient checkpointing - O(sqrt(n)) space tradeoff в production ML
Пространственная сложность: память тоже стоит денег

0

1

Войти