Относительно оперативного слияния в массиве
Я столкнулся со следующим вопросом.
Учитывая массив n элементов и целого числа k, где k <n. Элементы {a0... ak} и {ak+1...} уже отсортированы. Дайте алгоритм виду в O (n) время и O (1) пространство.
Это не кажется мне как он, может быть сделан в O (n) время и O (1) пространство. Проблема действительно, кажется, спрашивает, как сделать шаг слияния сортировки с объединением, но оперативный. Если бы это было возможно, разве сортируйте с объединением, то не был бы реализован тот путь? Я не могу убедить меня, хотя и нуждаются в некотором мнении.
2 ответа
Это , кажется, указывает на то, что это можно делать в пространстве O (lg ^ 2 n). Я не вижу, как доказать невозможность слияния в постоянном пространстве, но я тоже не вижу, как это сделать.
Изменить: Преследуя ссылки, Knuth Vol 3 - Exercise 5.5.3 говорит: «Значительно более сложный алгоритм Л. Трабба-Пардо дает наилучший возможный ответ на эту проблему: можно выполнить стабильное слияние за время O (n) и стабильную сортировку за время. Время O (n lg n), используя только O (lg n) бит вспомогательной памяти для фиксированного числа индексных переменных.
Еще ссылки , которые я не читал. Спасибо за интересную проблему.
Дальнейшее редактирование: В этой статье утверждается, что в статье Хуанга и Лэнгстона есть алгоритм, который объединяет два списка размера m и n за время O (m + n), поэтому ответ на ваш вопрос будет положительным. К сожалению, у меня нет доступа к статье, поэтому я должен доверять информации из вторых рук. Я не уверен, как согласовать это с заявлением Кнута о том, что алгоритм Трабба-Пардо является оптимальным. Если бы от этого зависела моя жизнь, я бы пошел с Кнутом.
Теперь я вижу, что этот вопрос задавался как и ранее, вопрос о переполнении стека число раз. У меня нет духа отмечать это как дубликат.
Хуан Б.-К. и Лэнгстон М. А. Практическое слияние на месте, Comm. ACM 31 (1988) 348-352
Нет, это невозможно, хотя моя работа была бы намного проще, если бы это было :).
У вас есть коэффициент O (log n), которого вы не можете избежать. Вы можете выбрать время или пространство, но единственный способ избежать этого - не сортировать. С пространством O (log n) вы можете создать список продолжений, который будет отслеживать, где вы спрятали элементы, которые не совсем подходят. С помощью рекурсии это можно сделать так, чтобы оно уместилось в куче O (1), но это только при использовании вместо этого фреймов стека O (log n).
Вот прогресс сортировки слиянием шансов и совпадений с 1 по 9. Обратите внимание, как вам требуется учет пространства журнала для отслеживания инверсий порядка, вызванных двойными ограничениями постоянного пространства и линейных свопов.
. -
135792468
. -
135792468
: .-
125793468
: .-
123795468
#.:-
123495768
:.-
123459768
.:-
123456798
.-
123456789
123456789
Есть некоторые деликатные граничные условия, которые немного сложнее, чем двоичный поиск, получить правильно, и даже в этой (возможной) форме, и, следовательно, плохая домашняя задача; но действительно хорошее умственное упражнение.
Обновление Видимо, я ошибаюсь, и есть алгоритм, который предоставляет время O (n) и пространство O (1). Я скачал документы, чтобы просветиться, и забираю этот ответ как неправильный.