Пространственная сложность сортировки слиянием в неизменяемом массиве

Пространственная сложность сортировки слиянием составляет O(n), а метод выглядит как void sort(int[] arr).

Если я создам метод int[] sort(int[] arr), который не изменяет входной массив, а возвращает новый отсортированный, то какова будет пространственная сложность этого метода/алгоритма?


algorithm space-complexity
person A5300    schedule 10.01.2019    source источник
comment
O(2*n) = O(n). Что сделает ваш метод, так это скопирует ввод и выполнит сортировку этой копии, а затем вернет ее. Почему вы ожидаете чего-то другого, кроме O(n)?   -  person Nelfeal    schedule 10.01.2019

Ответы (1)


arrow_upward
0
arrow_downward

Зависит от реализации сортировки слиянием.

рекурсивный

Поскольку вы не можете изменить входной массив в каждом рекурсивном вызове, пространственная сложность алгоритма равна S(n) = 2S(n/2) + n. Следовательно, S(n) = Theta(n log n).

повторяющийся

Если реализация сортировки слиянием не является рекурсивной (итеративной сортировки слиянием), вы можете скопировать входной массив в изменяемый массив и отсортировать этот массив на месте. Следовательно, пространственная сложность этой реализации сортировки слиянием равна Theta(n).

person OmG    schedule 10.01.2019
comment
Вам не нужно рекурсивно выполнять сортировку слиянием. - person Mark Ransom; 10.01.2019
comment
Теперь у вас другая проблема. Вы говорите о встроенной сортировке, но сложно/невозможно выполнить сортировку слиянием на месте. Надеюсь, я просто неправильно понимаю, что вы говорите. - person Mark Ransom; 10.01.2019
comment
@MarkRansom — это встроенная реализация сортировки слиянием: geeksforgeeks.org/iterative-merge-sort (просто скопируйте код слияния в его вызывающее место). Следовательно, это сложно, но не невозможно. - person OmG; 10.01.2019
comment
А, я вижу - скопировав ввод перед запуском, вы можете перезаписать его выводом. Это даже не сложно, но это не то, о чем я думал как на месте. - person Mark Ransom; 10.01.2019
comment
Сортировка слиянием на месте возможна, но не очень практична. Это будет медленнее, чем стандартная сортировка слиянием. Насколько медленнее, зависит от размера используемого вами промежуточного буфера. Асимтотически это O (n ^ 2 log (n)). Вы можете сделать это с постоянным дополнительным пространством, но если бы вы могли складывать кадры для рекурсивных вызовов, вы должны включить стоимость памяти O (log n). И, как указал Марк Рэнсом, если вы не можете изменить исходный массив, то его копирование будет стоить O(n). - person Jim Mischel; 10.01.2019
comment
@JimMischel Слияние на месте - это только O (n (log n) ^ 2), и оно настолько практично, что STL предлагает его. - person user58697; 10.01.2019
comment
@ user58697 Вы правы: O (n log (n) ^ 2). Не знаю, о чем я думал, когда писал это. Тем не менее, этот термин log(n)^2 немного пугает для больших наборов данных (миллионы и более). Конечно, это лучше, чем экспоненциальный член n. Но мне интересно, как это работает по сравнению с сортировкой кучи. Думаю, мне нужно сделать некоторые тесты. - person Jim Mischel; 10.01.2019