Временная сложность отвечает на вопрос «сколько работы?», а сложность по памяти — на вопрос «сколько памяти нужно?». Её тоже считают как функцию от размера входа n и записывают той же нотацией O.
Память входа и дополнительная память
Сами входные данные всегда занимают O(n), поэтому в анализе обычно считают только дополнительную (auxiliary) память: новые переменные, списки, словари и стек вызовов, которые алгоритм создаёт сверх входа. Алгоритм с дополнительной памятью O(1) работает на месте (in-place).
Разворот списка: копия и на месте
Первая функция строит новый список — дополнительная память O(n). Вторая двигает два индекса навстречу друг другу и меняет элементы местами — дополнительная память O(1). Время у обеих O(n), различие только в памяти.
