Память: на месте, вспомогательная, стек

Если знаешь, что такое вспомогательная память, «на месте» и почему стек рекурсии считается памятью, - листай до «Теперь сам».

Как думаешь, какой из двух дешевле по памяти

Развернуть список задом наперёд можно двумя способами:

# A: меняем местами концы, двигаясь к центру
levo, pravo = 0, len(a) - 1
while levo < pravo:
    a[levo], a[pravo] = a[pravo], a[levo]
    levo, pravo = levo + 1, pravo - 1

# B: собираем новый список задом наперёд
b = a[::-1]

Оба разворачивают за линейное время. Но A перекладывает внутри того же списка - лишней памяти ноль, а B заводит второй список на n элементов. По времени одно и то же, а по ВСПОМОГАТЕЛЬНОЙ памяти пропасть: у A её O(1), у B O(n). Значит «сколько стоит развернуть» - вопрос и про время, и про память.

На что это похоже

Переставить книги на одной полке - это способ A: работаешь в том же месте, лишнего пространства не нужно. Скопировать книги на вторую полку в обратном порядке - способ B: труд тот же, но нужна ещё целая полка. Вспомогательная память - это и есть «сколько ещё полок понадобится сверх той, на которой уже стоят данные».

Механизм: полная память, вспомогательная, «на месте»

Полная память - это вход плюс всё, что алгоритм завёл дополнительно. Вход есть всегда и у всех, поэтому сравнивают по вспомогательной памяти - той, что СВЕРХ входа. Алгоритм работает на месте, если вспомогательной памяти у него O(1): он обходится постоянным числом лишних ячеек, сколько бы ни было данных (разворот A - именно такой). Если он строит копию или новую структуру на n элементов, вспомогательная память O(n) (разворот B).

Отдельная и часто забываемая статья - стек рекурсии. Каждый незавершённый вызов держит кадр (аргументы, локальные, адрес возврата - из раздела про рекурсию), и на стеке одновременно лежит путь от корня до текущего вызова. Значит рекурсия глубины d стоит O(d) вспомогательной памяти, даже если сама ничего не выделяет и не возвращает. Глубина - это память, и её никто не пишет явно.

Правило

Вспомогательная память - то, что алгоритм занимает сверх входа. O(1) сверх входа - работа «на месте»; O(n) - копия. Стек рекурсии глубины d - это O(d) вспомогательной памяти. Сравнивают алгоритмы по вспомогательной, а не полной: вход у всех одинаков.

Разбор: две сортировки по памяти

Сортировка слиянием сливает две половины через отдельный буфер на n элементов - это O(n) вспомогательной памяти, плюс стек рекурсии O(log n) (глубина деления пополам). Итог - O(n): буфер перевешивает. Поэтому её называют НЕ работающей на месте.

Быстрая сортировка делит массив перестановками внутри него самого - разбиение идёт на месте, O(1) лишних ячеек на шаг. Но рекурсия остаётся: при сбалансированном делении стек O(log n), при вырожденном (тот самый худший вход из прошлого урока) - O(n). Итог - O(log n) в типичном случае. Отсюда и практическое преимущество: та же n·log n по времени, но памяти на порядок меньше, чем у слияния.

Разбор: время и память меняют друг на друга

Найти, есть ли в списке повтор, можно двумя способами с разным балансом. Сравнить все пары - O(n²) времени, зато O(1) памяти: лишних ячеек не нужно. Сложить виденное в множество и проверять по нему - O(n) времени, но O(n) памяти: множество разрастается до n элементов. Результат один и тот же, а цена разная - первый способ экономит память ценой времени, второй наоборот. Это типичный размен: почти всякое ускорение памятью оплачивается, и выбор зависит от того, чего не хватает - секунд или байтов. Поэтому у алгоритма спрашивают обе оценки сразу, а не одну.

Что ломается без этого

Две ошибки. Первая - назвать алгоритм работающим «на месте», забыв про стек рекурсии или буфер: рекурсивный обход глубины n не на месте, у него O(n) стека, даже если он не завёл ни одного массива. Вторая - не заметить, что копия удваивает память: на больших данных O(n) вспомогательной памяти может не влезть, и тогда решение «на месте» - единственное возможное, даже если оно чуть медленнее.

Зачем это в работе

Память - это ограничение не мягче времени. На встроенных устройствах и при обработке данных, которые не влезают в оперативку целиком, O(1) или O(log n) вспомогательной памяти - разница между «работает» и «не запускается». А ещё память и время часто МЕНЯЮТ друг на друга: хеш-таблица тратит O(n) лишней памяти, чтобы искать за O(1) вместо O(n). Выбор всегда парный - и по времени, и по памяти.

Теперь сам

Сколько вспомогательной памяти у разворота A, у разворота B и у рекурсивного обхода списка-цепочки из n узлов?