Quicksort часто описывается как in situ (на месте) алгоритм, несмотря на то, что для него требуется пространство стека O (log n). Таким образом, in situ означает, что «требуется меньше, чем O (n) дополнительного пространства» или пространство стека обычно не считается сложностью пространства (но почему это так?), Или это Quicksort фактически не in situ алгоритм?Обязательно Быстросортировать на месте (на месте) или нет?
Быстрое сокращение на самом деле не алгоритм in situ?
Стандартная реализация этого является нена месте. Это ужасно распространенное заблуждение, но вы, как правильно заметили, из-за потребления пространства стека, эта концепция ошибочна.
Я говорю «стандартная реализация» этого, потому что люди модифицировали алгоритм, чтобы сделать его O(1) -пространственным алгоритмом. Вот один пример: Quicksort without a stack.
Конечно, в соответствии с классическим space-time tradeoff такие версии quicksort менее эффективны, чем стандартная реализация.
Википедия предлагает следующее definition:
В информатике, алгоритм на месте (или в латинском на месте) представляет собой алгоритм, который преобразует входной сигнал, используя структуру данных, с небольшой, постоянной величиной дополнительного пространства для хранения.
По этому определению, типичный стек на основе быстрой сортировки явно не на месте алгоритм.
В самом деле, в статье Википедии явно говорит об этом:
алгоритм иногда неофициально называют на месте до тех пор, как он переписывает свой вход с выходом. На самом деле этого недостаточно (, как видно на примере quicksort) и не нужно; выходное пространство может быть постоянным или даже не подсчитываться, например, если выход является потоком.
и
Quicksort обычно описывается как алгоритм на месте, но это на самом деле не один. Для большинства реализаций требуется пространство O (log n) для поддержки рекурсии его разделения и завоевания.
Однако, как отметил @Jason в своем превосходном ответе, существуют варианты вариантов быстрой сортировки, которые требуют только O (1) дополнительного пространства. Любые такие алориты считаются in situ.
Этот вопрос задан раньше: http://cstheory.stackexchange.com/q/9563/6586. По сути, это скорее пламенная приманка с множеством противоречивых аргументов. – jpalecek
Обратите внимание, что это действительно зависит от того, как вы хотите определить * in-situ *.ЕСЛИ вы просто сравниваете алгоритмы сортировки, было бы очень неудобно не учитывать, что quicksort находится на месте, но если у вас есть более формальное определение в виду (надеюсь, по какой-то причине), тогда имеет смысл прекратить игнорировать небольшую деталь O (log n) , – hugomg
Это просто частный случай «O (log n), который также может быть большой константой», не так ли? В принципе Quicksort использует O (log n) дополнительное пространство. На практике вы обычно реализуете его, чтобы взять что-то вроде массива в качестве параметра. Массивы на большинстве языков имеют естественный верхний предел размера, основанный на типе фиксированной ширины, используемом для адреса и/или индексов, а Quicksort требуется только сохранить пару адресов на каждой из глубин «log n». Таким образом, использование стека постоянно ограничено практически для любой реализации Quicksort, которую вы когда-либо писали и использовали, даже если это не для «идеальной» версии. –