Коротко: оптимизация часто сводится к обмену памяти (space) на время (time): больше дополнительной памяти может убыстрить выполнение (кэш, таблицы, индексы), а экономия памяти обычно ведёт к большему времени вычислений (повторные вычисления, потоковая обработка, декомпрессия).
Примеры и пояснения (с комплексностями):
- Мемоизация vs рекурсивный пересчёт
- Наивный расчёт чисел Фибоначчи: время $O(2^n)$, память $O(n)$ (стек).
- С мемоизацией: время $O(n)$, память $O(n)$.
Вывод: жертвуя памятью $O(n)$ (таблица), вы снижаете экспоненциальное время до линейного.
- Таблицы соответствий / прекомпьютинг (lookup tables)
- Прекомпьютинг всех ответов: память $O(m)$, время запроса $O(1)$.
- Вычисление на лету: память $O(1)$, время запроса может быть значительным.
Применимо, когда число возможных входов невелико и важна латентность.
- Сортировки: in-place vs стабильные внешние алгоритмы
- Quicksort (в среднем): время $O(n\log n)$, дополнительная память $O(\log n)$ (рекурсивный стек).
- Mergesort (классический): время $O(n\log n)$, дополнительная память $O(n)$.
Вывод: если память ограничена — выбирают in-place алгоритмы (или tuning), если важна стабильность/предсказуемость времени — допускают дополнительную память ради mergesort.
- Представление графа: матрица смежности vs список смежности
- Матрица: память $O(n^2)$, проверка наличия ребра $O(1)$.
- Списки: память $O(n+m)$, проверка ребра $O(\mathrm{deg}(v))$.
Для плотных графов выгодна матрица (скорость), для разрежённых — списки (экономия памяти).
- Bloom filter и вероятностные структуры
- Позволяют экономить память по сравнению с точной структурой, но вводят ложные срабатывания и требуют $k$ хеш-функций на запрос (время $O(k)$).
Подходят, когда допустимы false positives ради существенной экономии памяти.
- Сжатие данных vs доступ/время декомпрессии
- Сжатые данные занимают меньше памяти/памяти на диске, но увеличивают CPU на сжатие/декомпрессию и задержку доступа.
Выбор зависит от пропускной способности диска/памяти и стоимости CPU.
- Внешняя память и потоковая обработка (streaming)
- Алгоритмы, работающие с потоками, используют $O(1)$ или $O(\log n)$ памяти, но могут требовать многократного чтения/пересчёта (больше I/O или CPU).
Нужны при ограниченной RAM и больших данных.
Практические рекомендации (когда жертвовать чем):
- Жертвуем временем ради памяти (т.е. экономим RAM): в embedded/мобильных системах, когда память критична или при ограничениях стоимости. Использовать стриминг, перерасчёт вместо кеша, компактные структуры, компрессию.
- Жертвуем памятью ради времени (т.е. ускоряем): когда важна низкая латентность/высокая пропускная способность и память доступна. Использовать кэши, индексы, прeкомпьютинг, дублирование данных.
- Учитывайте вторичные эффекты: большой кэш/таблицы могут ухудшить локальность и привести к кэшу CPU miss; сжатие снижает IO, но увеличивает CPU.
Краткая проверка при выборе: какие ресурсы критичны? (память, CPU, I/O, латентность). Каковы входные размеры и характер доступа (случайный/поточний)? Допустимы ли приближения/ошибки? Ответ на эти вопросы определяет, что лучше жертвовать.