Сложность по памяти и амортизация

Время — половина истории; интервьюер ждёт и оценку памяти.

Амортизированная сложность — это средняя стоимость одной операции в длинной серии операций, даже если отдельные операции бывают дорогими.

Память тоже считается

Когда говорят «решите за O(n) по времени и O(1) по памяти», имеют в виду дополнительную память сверх входа. Если вы создали новый массив длины n — это O(n) памяти. Если обошлись парой переменных — O(1). Это частый критерий «хорошего» решения: то же время, но меньше памяти.

Стек рекурсии — скрытая память

Каждый рекурсивный вызов кладёт кадр на стек. Рекурсия глубины n потребляет O(n) памяти, даже если внутри нет ни одного массива. Это легко забыть.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# глубина стека здесь = n
print(factorial(5))
print(factorial(10))

Вывод:

120
3628800

Что такое амортизация

Иногда одна операция дорогая, но в среднем по серии — дешёвая. Классика — динамический массив (в Python это list). Добавление в конец обычно O(1). Но когда массив заполнен, он выделяет вдвое больше памяти и копирует все элементы — это O(n). Кажется, что append дорогой? Нет: удвоения происходят редко, и суммарная стоимость n добавлений равна O(n), то есть O(1) на одно добавление амортизированно.

Как работает под капотом

Представим, что массив удваивается при заполнении. Чтобы добавить n элементов, копирования происходят на размерах 1, 2, 4, 8, ... — сумма этих копирований равна примерно 2n, то есть O(n) суммарно. Делим на n операций — получаем O(1) на операцию. Этот трюк называется «метод банкира»: дешёвые операции «откладывают монетки», которыми оплачивается редкая дорогая.

def cost_of_growth(n):
    capacity = 1
    total_copies = 0
    size = 0
    for _ in range(n):
        if size == capacity:
            total_copies += size  # копируем при удвоении
            capacity *= 2
        size += 1
    return total_copies

for n in [8, 16, 1000]:
    print("n =", n, "копирований:", cost_of_growth(n))

Вывод:

n = 8 копирований: 7
n = 16 копирований: 15
n = 1000 копирований: 1023

Видно: копирований примерно n, а не n^2. Значит на одно добавление приходится константа.

Частые ошибки

• Считать дополнительной памятью размер входа. Вход не считается — считается только то, что вы аллоцировали сами.
• Игнорировать стек рекурсии при оценке памяти.
• Думать, что один дорогой append делает весь цикл O(n^2). Амортизированно это O(n).

Итог

• Оценивайте дополнительную память отдельно от времени.
• Рекурсия глубины n — это O(n) памяти на стеке.
• Амортизация усредняет редкие дорогие операции по всей серии.