Разница в пространственной сложности различных алгоритмов сортировки

Когда вы запускаете код, память назначается двумя способами:

1. Неявно, когда вы настраиваете вызовы функций.

2. Явно, когда вы создаете куски памяти.

Быстрая сортировка — хороший пример неявного использования памяти. Пока я делаю быструю сортировку, я рекурсивно вызываю себя O(n) раз в худшем случае, O(log(n)) в среднем случае. Каждый из этих рекурсивных вызовов занимает O(1) места для отслеживания, что приводит к O(n) наихудшему случаю и O(log(n)) среднему случаю.

Сортировка слиянием — хороший пример явного использования памяти. Я беру два блока отсортированных данных, создаю место для слияния, а затем объединяю эти два блока в это слияние. Создание места для слияния — это O(n) данные.

Чтобы добраться до O(1) памяти, вам нужно как не назначать память, так и не вызывать себя рекурсивно. Это относится ко всем пузырьковым сортировкам, сортировкам вставками и сортировкам выбора.

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

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

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

Давайте рассмотрим быструю сортировку в качестве другого примера. Быстрая сортировка обычно не выделяет никакой внешней памяти, но ей нужно место для используемых кадров стека. Наивной реализации быстрой сортировки может потребоваться пространство (n) в худшем случае для кадров стека, если опорные точки всегда оказываются наибольшим или наименьшим элементом массива, поскольку в этом случае вы продолжаете рекурсивно вызывать функцию для массивов размера n - 1, n - 2, n - 3 и т. д. Однако есть стандартная оптимизация, которую вы можете выполнить, по сути, исключающую хвостовой вызов: вы рекурсивно вызываете быструю сортировку на меньшей из двух половин массива, затем повторно используете пространство стека из текущий вызов для большей половины. Это означает, что вы выделяете новую память только для рекурсивного вызова подмассивов размером не более n/2, затем n/4, затем n/8 и т. д., поэтому использование пространства падает до O(log n).

Я предполагаю, что массив, который мы сортируем, передается по ссылке, и я предполагаю, что пространство для массива не учитывается при анализе сложности пространства.

Пространственная сложность быстрой сортировки может быть сделана O(n) (и ожидаемой O(log n) для рандомизированной быстрой сортировки) с умной реализацией: например. не копируйте целые подмассивы, а просто передайте индексы.

O(n) для быстрой сортировки исходит из того факта, что количество "вложенных" рекурсивных вызовов может быть O(n): подумайте, что произойдет, если вы продолжите делать неудачный выбор для опорной точки. Хотя каждый кадр стека занимает O(1) места, может быть O(n) кадров стека. ожидаемая глубина (т. е. ожидаемое пространство стека) составляет O(log n), если мы говорим о рандомизированной быстрой сортировке.

Для сортировки слиянием я ожидаю, что сложность пространства будет O(log n), потому что вы делаете не более O(log n) "вложенных" рекурсивных вызовов.

Результаты, которые вы цитируете, также учитывают пространство, занимаемое массивами: тогда временная сложность сортировки слиянием составляет O(log n) для пространства стека плюс O(n) для массива, что означает O(n) общей сложности пространства. Для быстрой сортировки это O(n)+O(n)=O(n).