Сравни подходы к скорости памяти алгоритма и объясни, когда какой подход выбрать.

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

Компромисс время ↔ память (time-memory tradeoff)

Часто ускорение требует больше памяти, а экономия памяти — больше времени.

Подходы

Оптимизация по скорости (больше памяти)

• Кеширование/мемоизация — хранить результаты, не пересчитывать:

const cache = new Map(); // память ради скорости

• Хеш-таблицы — O(1) доступ ценой памяти (Map/Set вместо перебора):

const set = new Set(arr); // O(1) has вместо O(n) includes

• Предвычисления, индексы, lookup-таблицы.

Когда: скорость критична, память есть (интерактивный UI, частые операции).

Оптимизация по памяти (медленнее)

• Обрабатывать данные потоково (по частям), не грузить всё.
• Меньше структур, вычислять на лету вместо хранения.
• In-place алгоритмы (без доп. массивов).

Когда: память ограничена (большие данные, мобильные устройства), скорость менее важна.

Компромисс

Часто выбирают золотую середину: например, quicksort (O(log n) память, in-place) против merge sort (O(n) память, но стабильный).

Как выбирать

• Скорость критична, память есть → кеш/хеш-таблицы (жертвуем памятью).
• Память ограничена → потоковая обработка, in-place (жертвуем скоростью).
• Оценить реальные ограничения (размер данных, устройство) и профилировать.

Коротко для собеседования

Баланс скорость↔память (time-memory tradeoff): ускорение — кеш/мемоизация, хеш-таблицы (O(1) ценой памяти), предвычисления; экономия памяти — потоковая обработка, in-place, вычисление на лету (медленнее). Выбор по ограничениям: скорость критична и память есть → кеш; память ограничена → потоки/in-place. Пример — quicksort (мало памяти) vs merge sort (стабильный, но O(n)).