#algorithm #sorting #data-structures
#алгоритм #сортировка #структуры данных
Вопрос:
Предположим, что у вас есть волшебная структура данных, которая представляет линейную последовательность элементов, которая поддерживает поиск, вставку и удаление любого индекса в наихудшем случае за O (1) время. (Я почти уверен, что такая структура невозможна, учитывая модель памяти современных машин, но давайте просто предположим, что у нас есть одна для развлечения).
Мой друг отметил, что если у вас есть эта структура данных, то вы можете построить классный алгоритм сортировки для целых чисел, который выполняется за ожидаемое время O (n, lg, lg, n) следующим образом. Сначала создайте одну из волшебных структур данных, упомянутых выше. Далее, для каждого элемента во входном массиве используйте интерполяционный поиск, чтобы найти за ожидаемое время O (lg lg n) индекс в том волшебном массиве, к которому принадлежит элемент, затем за время O (1) вставьте элемент. Наконец, через O (n) раз считайте отсортированную волшебную структуру данных. Это приводит к n вызовам интерполяционного поиска O (lg lg n), который будет выполняться за O (n lg lg n) время.
Я понимаю, что этот описанный выше подход не даст в наихудшем случае O (nn) времени на сортировку, поскольку существуют патологически плохие входные массивы, которые при использовании в интерполяционном поиске привели бы к вырождению поиска до O (n, ,2,,,,) времени. Мой вопрос в том, учитывая эту волшебную структуру данных, какой самый быстрый алгоритм сортировки целых чисел, который может быть построен, предполагая, что мы заботимся только о наихудшем времени выполнения алгоритма?
(Возможно, это лучше подходит для cstheory, но я решил, что сначала спрошу здесь, поскольку в прошлом я получил ответы на несколько отличных алгоритмов.)
Комментарии:
1. Если бы мне было разрешено использовать волшебные структуры данных, я бы использовал ту, которая всегда была предварительно отсортирована. Тогда сортировка была бы
O(1)операцией.2. Этот вопрос, похоже, не по теме, потому что речь идет о теоретической конструкции CS, а не о практической задаче программирования.
Ответ №1:
Подсчет сортировки имеет O (n) сложность http://en.wikipedia.org/wiki/Counting_sort . Однако это не всегда удобно в использовании, потому что временный массив, который создается алгоритмом, имеет размер максимального целого значения отсортированного массива.
Комментарии:
1. Я не уверен, что понимаю, как можно выполнить подсчет сортировки за O (n) раз с этой структурой данных. Подсчет сортировки занимает O (n U) времени, где U — размер вселенной сортируемых элементов, и я не понимаю, как волшебный массив может исключить член U. Можете ли вы подробнее остановиться на этом?
2. @templatetypedef Мы можем исключить термин U, если будем использовать сортировку по счету в сочетании с сортировкой по основанию (мы можем это сделать, потому что сортировка по счету — это стабильная сортировка).
Ответ №2:
Любая сортировка на основе сравнения требует O(n log(n)) сравнений в среднем случае, не говоря уже о наихудшем. Смотрите http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list подробнее о том, почему. Поэтому никакая сортировка на основе сравнения не может превзойти этот нижний предел даже с вашей волшебной структурой данных.
Сортировки, не основанные на сравнении (например, radix), как правило, разрабатываются таким образом, чтобы они не извлекали выгоду из вашей структуры данных, поэтому я не думаю, что это имело бы для них значение.
Ответ №3:
Интерполяционный поиск требует операции, выходящей за рамки простого сравнения, и, следовательно, не может использоваться при сортировке сравнения. Если вы можете выполнить интерполяцию, вы, вероятно, сможете выполнять операции, подобные radix, и, таким образом, выполнять лучше, чем O (n log n), и волшебные структуры данных помогут.
Подсчет сортировки сортирует в O (n) в вашей магической структуре, что примерно так же быстро, как любой алгоритм сортировки целых чисел, вероятно, будет. Интересный и потенциально нерешенный вопрос заключается в том, насколько быстр самый быстрый алгоритм параллельной сортировки целых чисел. Учитывая бесконечное количество процессоров (например, в недетерминированной машине Тьюринга), я ожидаю, что вы сможете добиться большего, чем O (n), но я не знаю, насколько.