Сложность памяти быстрой сортировки

Пространственная сложность Quicksort является перечисленной как O(logn).

Однако - Quicksort может обрабатывать без использования какой-либо дополнительной памяти: на каждой итерации, во время процесса разбиения, записи меняются местами в конечном итоге, чтобы быть в левая и правая секции основаны на используемой оси вращения. эта рекурсивная замена-и-таким образом-формирование-разделов может быть сделано в самом списке, не имея разделы на одном уровне рекурсивных вызовов интерференции и без зыбучих водорослей различные уровни вмешательства вызовов.

Какая польза от дополнительной памяти в Quicksort?

ТИА.

//============================

Правка:

Согласен с пространством стека в комментариях / ответах - пропустил это.

Еще,

Быстрая сортировка выполняется в O(nlogn) Время ожидаемый случай-- путем формирования (почти) секций одинакового размера на каждом уровне рекурсии.

Используемое стековое пространство является двоичным деревом, полным деревом в оптимальный случай, с высотой log n. Каждый узел в этом дереве является рекурсивным вызовом, а стек-пространством в данном случае идет по порядку n -- Не log n. в этом дереве есть узлы O(n). рекурсивные вызовы влево и вправо разделы выполняются одновременно-дерево вызовов заполняется в определенный момент выполнения.

Итак - средняя сложность пространства случаев должна быть O(n)- не O(logn) (?)

Это также противоречит пространственной сложности слияния-сортировки. сложность пространства слияния-сортировки указана как O(n) и обрабатывает аналогично.
3 2
sorting algorithm data-structures complexity-theory quicksort

3 ответа:

Quicksort обычно использует o (log n) дополнительную память, хранящуюся в стеке. Это не O(n), потому что двоичное дерево никогда не является явным в памяти, мы просто выполняем его поступорядоченный обход (то есть: только один путь в дереве всегда сохраняется в данный момент времени).

Mergesort указан как O (n), потому что мы обычно копируем результат слияния в новый массив. Сортировка на месте возможна, но увеличивает временную сложность до O(N log2 н), согласно Википедии. Это все равно используйте O (log n) для рекурсии.

0

Пространство стека для рекурсии. то есть вам не нужно хранить какие-либо дополнительные Данные, но вам нужно хранить обратные адреса (EDIT: и другую связанную информацию, применимую к рассматриваемому языку, спасибо @dmaij за напоминание) для каждого рекурсивного подзвонка. Поскольку Quicksort генерирует стек глубины log(n), Вам потребуется столько же кадров стека одновременно в стеке вызовов.

0

Быстрая сортировка со случайными поворотами имеет пространственную сложность

Средний случай = O(logN)
худший вариант = O(N)

Наихудший случай возникает, когда род не сбалансирован. Однако этого можно избежать, сортируя сначала меньшие подрешетки, а затем хвостовую рекурсию на большем массиве. Эта улучшенная версия будет иметь сложность пространства наихудшего случая O(logN). Обратите внимание, что хвостовая рекурсия внутренне реализована большинством компиляторов, и для этого не требуется писать дополнительный код.

Сортировка слиянием имеет среднюю/наихудшую сложность пространства O(N), поскольку подпрограмма слияния копирует массив в новый массив, который требует O(N) дополнительного пространства.

Править: Как было предложено в комментариях, полагаться на хвостовую рекурсивную оптимизацию не очень хорошо. Было бы лучше включить его в код вместо этого.

0