In-place и O(1) по памяти: точные определения и пример на Python

Почему перенос в буфер не in-place и не O(1) по памяти; что такое strict in-place, учет стека; корректные итерационные и рекурсивные решения на Python.

Когда мы обсуждаем сложность по памяти и поведение «in-place», границы часто размываются, как только в дело вступают динамические массивы, стековые кадры и промежуточные структуры. Небольшой невинный фрагмент кода способен вызвать неожиданно сложную дискуссию. Например, функция, которая «сливает» список в другой, а потом переносит всё обратно. Это in-place? Это O(1) по памяти? Или временный список полностью меняет классификацию?

Постановка задачи

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

def flip_twice(seq):
    buf = []
    while seq:
        buf.append(seq.pop())
    while buf:
        seq.append(buf.pop())

Интуитивно может показаться, что поскольку общее число элементов неизменно и в любой момент len(seq) + len(buf) равно исходному размеру, дополнительная память будто бы «константная». Но классификация зависит от того, как память реально используется, а не только от суммарного сохранения объёма данных.

Что на самом деле говорят определения

Есть три полезных «оптики». Алгоритм называют in-place, если он использует лишь фиксированный объём дополнительной (вспомогательной) памяти и преобразует вход на месте. Более строгая трактовка — strict in-place — исключает любую неявную дополнительную память, например рост стека из‑за рекурсии или цепочек генераторов. Наконец, O(1) по памяти означает, что требуемая вспомогательная память не растёт с размером входа, даже если она «переезжает» в ходе вычислений. Все эти термины хорошо определены, хотя на практике люди иногда спорят, какой именно вид памяти — вспомогательные массивы или стек вызовов — следует учитывать. И именно поэтому важно заранее оговорить определения.

Почему пример не in-place и не O(1)

Функция выше выделяет новый список и заполняет его столькими же элементами, сколько было в исходном. Хотя исходный список уменьшается, а буфер растёт, вы не переиспользуете ту же область хранения: вы выделяете дополнительное место под элементы временного списка. С ростом входа растёт и временная структура. Значит, объём вспомогательной памяти масштабируется с размером входа. По определениям это не in-place, не strict in-place и не O(1) по памяти.

Также стоит отметить, что во время выполнения исходный список опустошается и затем собирается заново, то есть все данные фактически покидают исходный контейнер, прежде чем записываются обратно. Это ещё раз подчёркивает, что работа не ведётся на месте. Обсуждения иногда уводят в детали реализации динамических массивов, непрерывности памяти или того, как ведёт себя append; эти соображения не меняют классификацию в данном случае. Некоторые разработчики также спорят, считать ли append() операцией O(1), что дополнительно усложняет анализ времени, — но аргумент про память самодостаточен.

Действительно in-place альтернатива

Того же наблюдаемого промежуточного состояния — список развёрнут наполовину — можно добиться без выделения второго списка. Следующая версия меняет местами симметричные элементы на месте, затем делает это ещё раз, оставляя список как был.

def spin_twice(items):
    for k in range(len(items) // 2):
        items[k], items[-k - 1] = items[-k - 1], items[k]
    for k in range(len(items) // 2):
        items[k], items[-k - 1] = items[-k - 1], items[k]

Этот подход полностью работает в исходном хранилище. Он in-place, потому что все изменения происходят там, где живут данные. Он strict in-place, потому что нет рекурсии и другого неявного роста стека. И он использует O(1) вспомогательную память, поскольку объём дополнительной памяти не зависит от размера входа; сама итерационная механика ограничена. Если вывести временное состояние на середине первого прохода и сравнить его с функцией на буфере на середине её первого этапа, вы увидите один и тот же развёрнутый порядок.

Нестрогий in-place вариант

Если выразить ту же логику обменов рекурсивно, свойство in-place сохраняется, но строгость теряется из‑за растущей глубины вызовов. В зависимости от используемого определения стек может учитываться или нет при оценке O(1); в любом случае глубина рекурсии явно масштабируется с размером входа.

def spin_twice_rec(items, idx = 0):
    items[idx], items[-idx - 1] = items[-idx - 1], items[idx]
    if idx < len(items) // 2:
        spin_twice_rec(items, idx + 1)
    items[idx], items[-idx - 1] = items[-idx - 1], items[idx]

Это по‑прежнему in-place, потому что список изменяется напрямую, без выделения вспомогательных контейнеров. Но это уже не strict in-place, поскольку рекурсия вносит неявный рост стека по мере увеличения входа. Считать ли это O(1) по памяти зависит от того, включаете ли вы кадры стека в учёт; разумная позиция — что это не O(1).

Зачем важна разница

Оценки по памяти часто путают с деталями реализации или расплывчатыми формулировками вроде «всего один дополнительный список». Чёткие, общие определения позволяют оценивать код без догадок. Если вам нужно обосновать архитектурное решение, пересмотреть алгоритмические гарантии или проверить потребление памяти, разница между выделением временного буфера и обменом на месте имеет значение. Кроме того, нередко заявляют O(1) по памяти для шаблонов, которые на самом деле выделяют дополнительную память, вероятно, сосредоточившись на сохранении числа элементов, а не на том, где эти элементы находятся во время выполнения. Когда разговор привязываешь к вспомогательной памяти, неявному стеку и преобразованию на месте, классификация становится однозначной.

Выводы

Классифицируйте память, явно указывая, что вы учитываете. Если ваше определение включает вспомогательные структуры и неявные стековые кадры, подход с буфером не является ни in-place, ни O(1), тогда как итерационный обмен — strict in-place и O(1). Если вы выбираете определение, исключающее стек, рекурсивный обмен можно по‑прежнему называть in-place, но он не будет строгим. Если хотите убедиться в промежуточных состояниях, добавьте в оба варианта вывод на середине выполнения и сравните наблюдаемый порядок элементов. И самое важное — заранее договоритесь об определениях, чтобы не говорить мимо друг друга.