Как сортировка слиянием имеет пространственную сложность O (n) для наихудшего случая?

Сложность O(n) означает, что сортировка слиянием в худшем случае занимает пространство памяти, равное количеству элементов, присутствующих в исходном массиве. Но разве он не создал новые массивы при выполнении рекурсивных вызовов? Как это место не считается?


sorting algorithm mergesort complexity-theory space-complexity
person Aishwarya R    schedule 12.01.2016    source источник
comment
Как вы думаете, почему он не создает новые массивы? Он должен копировать элементы в новые массивы для каждого шага слияния.   -  person OneCricketeer    schedule 12.01.2016
comment
См. это, stackoverflow.com/questions/ 10342890/   -  person zangw    schedule 12.01.2016
comment
Вы имеете в виду служебную память при создании новых массивов?   -  person ferit    schedule 12.01.2016
comment
Даже 5n + 999 равно O(n).   -  person greybeard    schedule 12.01.2016

Ответы (4)


arrow_upward
2
arrow_downward

В худшем случае реализация сортировки слиянием сверху вниз может занять больше места, чем исходный массив, если она выделяет обе половины массива в mergesort() перед выполнением рекурсивных вызовов самой себе.

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

В случае сортировки слиянием снизу вверх можно использовать временный массив в 1/2 размера исходного массива, объединяя обе половины массива, в результате чего первая половина данных находится во временном массиве, а вторая половина в исходном массиве, а затем выполнить окончательное слияние обратно в исходный массив.

Однако пространственная сложность равна O(n) в любом случае, поскольку константы типа 2 или 1/2 игнорируются для большого O.

person rcgldr    schedule 12.01.2016

arrow_upward
1
arrow_downward

MergeSort достаточно одного буфера того же размера, что и исходный массив.

В обычной версии вы выполняете слияние из массива в дополнительный буфер и копируете обратно в массив.

В расширенной версии вы выполняете слияния из массива в дополнительный буфер и наоборот, попеременно.

person Yves Daoust    schedule 12.01.2016

arrow_upward
0
arrow_downward

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

Сортировку слиянием легко реализовать, чтобы использовать один и тот же массив для всего без создания новых массивов. Просто отправьте границы в каждом рекурсивном вызове. Что-то вроде этого (в псевдокоде):

mergesort(array) ->
    mergesort'(array, 0, length of array - 1)

mergesort'(array, start, end) ->
    mergesort'(array, start, end/2)
    mergesort'(array, end/2+1, end)
    merge(array, start, end/2, end/2+1, end)

merge(array, start1, end1, start2, end2) ->
    // This function merges the two partitions
    // by just moving elements inside array
person Emil Vikström    schedule 12.01.2016
comment
То, что вы описываете, представляет собой сортировку слиянием на месте, и ее не легко реализовать. stackoverflow.com/questions/2571049/ - person Karoly Horvath; 12.01.2016
comment
Вы действительно правы. Моя ошибка! Я оставлю это как пример того, как непродуманность чего-то может привести к неправильному выводу. - person Emil Vikström; 12.01.2016

arrow_upward
-1
arrow_downward

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

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

person sarjit07    schedule 13.01.2016