Что такое компромисс между временем и памятью?

У алгоритма две основные характеристики: время и дополнительная память. Их часто можно обменивать друг на друга.

Память в обмен на время:

• хеш-множество — проверка «видели ли мы элемент» за O(1) вместо O(n), ценой O(n) памяти. Поиск пары с заданной суммой: O(n²) вложенным циклом или O(n) с множеством;
• мемоизация — запоминаем результаты функции, чтобы не считать их повторно: числа Фибоначчи из O(2ⁿ) превращаются в O(n);
• предвычисление — префиксные суммы дают сумму любого отрезка за O(1) после O(n) подготовки;
• индекс в базе данных — дополнительная структура на диске, но поиск за O(log n) вместо полного просмотра;
• кэш — хранить готовые ответы на частые запросы.

Время в обмен на память: сортировка на месте (пирамидальная, O(1) памяти) вместо сортировки слиянием (O(n) дополнительной памяти); пересчитывать значение каждый раз вместо хранения; потоковая обработка данных частями, когда всё не помещается в память.

Что выбрать — зависит от ограничений задачи: сколько данных, сколько памяти, как часто выполняется операция. На собеседовании хорошо явно проговорить: «можно за O(n) времени и O(n) памяти или за O(n log n) и O(1)».

def two_sum(nums, target):
    seen = {}                          # O(n) памяти...
    for i, x in enumerate(nums):
        if target - x in seen:         # ...за проверку O(1) вместо прохода
            return seen[target - x], i
        seen[x] = i
    return None