Как соотносятся временная и пространственная сложность алгоритма?

Временная сложность мерит число операций, пространственная — объём дополнительной памяти; между ними почти всегда есть компромисс: ускорение покупается памятью и наоборот.

Классические trade-off

• Мемоизация и кеши: храним результаты вычислений — платим O(n) памяти за ускорение с экспоненты до O(n).
• Хеш-таблица: поиск за O(1) вместо O(n) ценой O(n) дополнительной памяти.
• Сортировки: mergesort стабилен и O(n log n), но требует O(n) буфера; heapsort обходится O(1) памяти, но нестабилен и медленнее по константам.

Что считается памятью

• Глубина рекурсии — тоже пространственная сложность: рекурсивный DFS на дереве глубины h потребляет O(h) стека.
• In-place алгоритмы тратят O(1) дополнительной памяти, не считая самого входа.

На собеседовании

Уточняйте ограничения: при ограниченной памяти (стриминг, встроенные системы) выбирают менее прожорливый алгоритм даже ценой времени.

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

Время и память обычно обмениваются друг на друга: кеш, мемоизация или хеш-таблица ускоряют алгоритм ценой дополнительной памяти. Не забывайте учитывать стек рекурсии, а при жёстком лимите памяти выбирайте более экономный алгоритм, даже если он медленнее.