Quicksort часто описывается как алгоритм in situ (на месте), несмотря на то, что для него требуется пространство стека O (log n). Таким образом, in situ означает, что "требуется меньше O (n) дополнительного пространства" или пространство стека обычно не считается пространственной сложностью (но почему это так?), Или Quicksort фактически не является алгоритмом in situ?
Обязательно ли Quicksort in situ (на месте) или нет?
Ответ 1
является Quicksort фактически не алгоритмом in situ?
Стандартная реализация - не на месте. Это ужасно распространенное заблуждение, но вы, как правильно заметили, из-за потребления пространства стека, эта концепция ошибочна.
Я говорю "стандартную реализацию" этого, потому что люди модифицировали алгоритм, чтобы сделать его O(1) -пространственным алгоритмом. Вот один пример: Quicksort без стека.
Конечно, в соответствии с классическим пространственно-временным компромиссом такие версии quicksort менее эффективны, чем стандартная реализация.
Ответ 2
Википедия предлагает следующее определение:
В информатике алгоритм на месте (или на латинском языке in situ) является алгоритмом, который преобразует входные данные с использованием структуры данных с небольшим постоянным количеством дополнительного пространства для хранения.
В соответствии с этим определением типичная быстродействующая система на основе стекол явно не является алгоритмом in situ.
Фактически, статья Википедии явно обсуждает это:
Алгоритм иногда неофициально называется in-place, если он перезаписывает свой вход своим выходом. На самом деле этого недостаточно (, как демонстрирует quicksort), и это не обязательно; выходное пространство может быть постоянным или даже не подсчитываться, например, если выход является потоком.
и
Quicksort обычно описывается как алгоритм на месте, но на самом деле он не является. Для большинства реализаций требуется пространство O (log n) для поддержки его рекурсии и рекурсии.
Однако, как отметил @Jason в своем превосходном ответе, существуют варианты вариантов быстрой сортировки, которые требуют только O (1) дополнительного пространства. Любые такие алориты будут рассматриваться in situ.