X + Y сортировка - X + Y sorting

В Информатика, Икс + Y сортировка это проблема сортировка пары номеров по их сумме. Для двух конечных множеств Икс и Y, обе одинаковой длины, проблема состоит в том, чтобы заказать все пары (Икс, у) в Декартово произведение Икс × Y в числовом порядке по значению Икс + у. Проблема связана с Элвин Берлекамп.^[1][2]

Классическая сортировка сравнения

Нерешенная проблема в информатике: Есть ${\displaystyle X+Y}$ алгоритм сортировки быстрее, чем ${\displaystyle O(n^{2}\log n)}$? (больше нерешенных проблем в информатике)

Эту проблему можно решить с помощью простого сортировка сравнения на декартовом произведении двух данных множеств. Когда наборы имеют размер ${\displaystyle n}$, их товар имеет размер ${\displaystyle n^{2}}$, а время для алгоритма сортировки сравнения равно ${\displaystyle O(n^{2}\log n)}$. Это лучший известный на тот момент верхний предел для данной проблемы. Ли ${\displaystyle X+Y}$ сортировка может выполняться в более медленно растущие сроки - это открытая проблема.^[3][2]

Харпер и др. (1975) предлагаю отдельно сортировку ${\displaystyle X}$ и ${\displaystyle Y}$, а затем построение двумерной матрицы значений ${\displaystyle X+Y}$ который сортируется как по строкам, так и по столбцам перед использованием этих частично отсортированных данных для завершения сортировки ${\displaystyle X+Y}$. Хотя это может уменьшить количество необходимых сравнений на постоянный коэффициент, по сравнению с простой сортировкой сравнения, они показывают, что любой алгоритм сортировки сравнения, который может работать для произвольных ${\displaystyle n\times n}$ матрицы, отсортированные по строкам и столбцам, по-прежнему требуют ${\displaystyle \Omega (n^{2}\log n)}$ сравнения, поэтому дополнительная информация о наборе ${\displaystyle X+Y}$ сверх этого упорядочения матриц потребуется для любого более быстрого алгоритма сортировки.^[1]

Количество заказов

Числа в двух списках ввода для ${\displaystyle X+Y}$ проблему сортировки можно интерпретировать как Декартовы координаты точки в ${\displaystyle 2n}$-мерное пространство ${\displaystyle \mathbb {R} ^{2n}}$. Если кто-то разбивает пространство ${\displaystyle \mathbb {R} ^{2n}}$ в ячейки, поэтому набор ${\displaystyle X+Y}$ имеет фиксированный порядок внутри каждой ячейки, тогда границы между этими ячейками гиперплоскости определяется равенством пар ${\displaystyle x_{i}+y_{j}=x_{k}+y_{\ell }}$. Количество гиперплоскостей, которое можно определить таким образом, равно ${\displaystyle {\tbinom {n}{2}}^{2}=O(n^{4})}$, и количество ячеек, которое это количество гиперплоскостей может разделить пространство размерности ${\displaystyle 2n}$ в меньше чем ${\displaystyle n^{8n}}$. Следовательно, множество ${\displaystyle X+Y}$ имеет самое большее ${\displaystyle n^{8n}}$ различные возможные заказы.^[1][4]

Количество сравнений

Количество сравнений, необходимое для сортировки ${\displaystyle X+Y}$ конечно ниже, чем при обычной сравнительной сортировке: Майкл Фредман показал в 1976 году, что ${\displaystyle X+Y}$ сортировку можно произвести, используя только О(п²) сравнения. В более общем плане он показывает, что любой набор ${\displaystyle N}$ элементы, сортировка которых уже ограничена семейством ${\displaystyle \Gamma }$ заказов, можно отсортировать с помощью ${\displaystyle \log _{2}|\Gamma |+O(N)}$ сравнения, по форме сортировка двоичной вставкой. Для ${\displaystyle X+Y}$ проблема сортировки, ${\displaystyle N=n^{2}}$, и ${\displaystyle |\Gamma |\leq n^{8n}}$, так ${\displaystyle \log _{2}|\Gamma |=O(n\log n)}$ и оценка Фредмана означает, что только ${\displaystyle O(n^{2})}$ сравнения нужны. Однако время, необходимое для принятия решения о том, какие сравнения выполнить, может быть значительно больше, чем ограничение на количество сравнений.^[4] Если бы только сравнения между элементами ${\displaystyle X+Y}$ разрешены, то существует также соответствующая нижняя граница ${\displaystyle \Omega (n^{2})}$ по количеству необходимых сравнений.^[4][5]

Первый реальный алгоритм, который достигает обоих ${\displaystyle O(n^{2})}$ сравнения и ${\displaystyle O(n^{2}\log n)}$ Общая сложность была опубликована шестнадцатью годами позже. Сначала алгоритм рекурсивно сортирует два набора ${\displaystyle X+X}$ и ${\displaystyle Y+Y}$, и использует эквивалентность ${\displaystyle x_{i}-x_{j}\leq x_{k}-x_{\ell }\Leftrightarrow x_{i}+x_{\ell }\leq x_{j}+x_{k}}$ вывести отсортированный порядок ${\displaystyle X-X}$ и ${\displaystyle Y-Y}$ без дополнительных сравнений. Затем он объединяет два набора ${\displaystyle X-X}$ и ${\displaystyle Y-Y}$ и использует объединенный порядок и эквивалентность ${\displaystyle x_{i}+y_{j}\leq x_{k}+y_{\ell }\Leftrightarrow x_{i}-x_{k}\leq y_{\ell }-y_{j}}$ вывести отсортированный порядок ${\displaystyle X+Y}$ без дополнительных сравнений. Часть алгоритма, рекурсивно сортирующая ${\displaystyle X+X}$ (или эквивалентно ${\displaystyle Y+Y}$) делает это путем разделения ${\displaystyle X}$ на два равных подсписка ${\displaystyle A}$ и ${\displaystyle B}$, рекурсивная сортировка ${\displaystyle A+A}$ и ${\displaystyle B+B}$, подразумевая заказ на ${\displaystyle A+B}$ как указано выше, и объединение отсортированных результатов ${\displaystyle A+A}$, ${\displaystyle B+B}$, и ${\displaystyle A+B}$ вместе.^[6]

Алгоритмы, не основанные на сравнении

На RAM машина с размер слова ш и целочисленные входы 0 ≤ {Икс, у} < п = 2^ш, проблема может быть решена в О(п бревно п) операции с помощью быстрое преобразование Фурье.^[1]

Приложения

Стивен Скиена рассказывает о практическом применении в пути транспортные расходы минимизация, экземпляр проблема кратчайшего пути: данные тарифы Икс и у для поездок из пункта отправления A в промежуточный пункт назначения B и из пункта B в пункт назначения C, когда разрешено комбинировать только определенные пары тарифов, найдите самый дешевый объединенный рейс из пункта A в C. Решение Skiena состоит в сортировке пар тарифов как экземпляр ${\displaystyle X+Y}$ проблема сортировки, а затем тестирование полученных пар в этом отсортированном порядке, пока не будет найдена разрешенная. Для этой задачи можно использовать приоритетная очередь пар, инициализированных, чтобы содержать одну пару с самой дешевой общей парой тарифов. Тогда, когда пара ${\displaystyle (x,y)}$ оказывается запрещенным, еще две пары образуются путем объединения ${\displaystyle x}$ и ${\displaystyle y}$ с их преемниками в соответствующих отсортированных списках тарифов с одним прыжком, могут быть добавлены (если еще не представлены) в очередь приоритетов. Таким образом, каждая последующая пара может быть найдена за логарифмическое время, и нужно отсортировать только пары до первой допустимой.^[3]

Несколько других проблем в вычислительная геометрия иметь эквивалентную или более сложную сложность ${\displaystyle X+Y}$ сортировка, в том числе построение Суммы Минковского многоугольников лестниц, нахождение точек пересечения расположение линий в отсортированном порядке по их ${\displaystyle x}$-координаты, перечисление пар точек в отсортированном порядке по их расстояниям и проверка того, прямолинейный многоугольник может быть переведено так, чтобы соответствовать другому.^[7]

Смотрите также

• 3SUM
• Целочисленная сортировка

Рекомендации

1. Harper, L.H .; Payne, T. H .; Сэвидж, Дж. Э.; Штраус, Э. (1975). «Сортировка X + Y». Коммуникации ACM. 18 (6): 347–349. Дои:10.1145/360825.360869.
2. Демейн, Эрик; Эриксон, Джефф; О'Рурк, Джозеф (20 августа 2006 г.). «Задача 41: Сортировка X + Y (попарные суммы)». Проект открытых проблем. Получено 23 сентября 2014.
3. Скиена, Стивен (2008). «4.4 Военная история: Дайте мне билет на самолет». Руководство по разработке алгоритмов (2-е изд.). Springer. С. 118–120. Дои:10.1007/978-1-84800-070-4_4.
4. Фредман, Майкл Л. (1976). «Насколько хорошо теория информации связана с сортировкой?». Теоретическая информатика. 1 (4): 355–361. Дои:10.1016/0304-3975(76)90078-5.
5. Дицфельбингер, Мартин (1989). «Нижние оценки для сортировки сумм». Теоретическая информатика. 66 (2): 137–155. Дои:10.1016/0304-3975(89)90132-1. МИСТЕР  1019082.
6. Ламбер, Жан-Люк (1992). «Сортировка сумм (Икс_я + у_j) в О(п²) сравнения ». Теоретическая информатика. 103 (1): 137–141. Дои:10.1016 / 0304-3975 (92) 90089-X.
7. Эрнандес Баррера, Антонио (1996). "Нахождение о(п² бревно п) алгоритм иногда бывает сложным " (PDF). Труды 8-й Канадской конференции по вычислительной геометрии (CCCG'96). С. 289–294.