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

Не путать с проблемой XY .

Нерешенная задача в информатике :

Есть ли $X+Y$ алгоритм сортировки быстрее, чем $O(n^{2}\log n)$?

(еще нерешенные проблемы по информатике)

Геометрическая визуализация $X+Y$ проблема с сортировкой. Входные наборы $X$ и $Y$ представлены наборами вертикальных и горизонтальных черных линий (соответственно), и цель задачи — отсортировать точки пересечения по положению проходящих через них красных диагональных линий.

В информатике , ${\boldsymbol {X}}+{\boldsymbol {Y}}$ Сортировка — это задача сортировки пар чисел по их суммам. Приложения этой проблемы включают транзитных тарифов минимизацию , проектирование СБИС и умножение разреженных полиномов . Как и в случае с сортировкой сравнения и сортировкой целых чисел в более общем плане, алгоритмы для этой задачи могут быть основаны только на сравнении этих сумм или на других операциях, которые работают только тогда, когда входные данные представляют собой небольшие целые числа.

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

Постановка задачи и история

Вход в $X+Y$ задача сортировки состоит из двух конечных наборов чисел $X$ и $Y$, той же длины. Результатом задачи является сбор всех пар чисел из $X$ и номер из $Y$, упорядоченные по сумме каждой пары. В качестве небольшого примера для входных данных $X=\{1,2,9\}$ и $Y=\{0,4,9\}$, на выходе должен быть список пар $$(1,0),\,(2,0),\,(1,4),\,(2,4),\,(9,0),\,(1,9),\,(2,9),\,(9,4),\,(9,9)$$одного элемента из $X$ и один элемент из $Y$, перечисленные в отсортированном порядке по суммам пар $$1,2,5,6,9,10,11,13,18.$$Одним из способов решения проблемы было бы создание сортируемых пар ( декартово произведение двух коллекций) и использование этих пар в качестве входных данных для стандартного алгоритма сортировки сравнения, такого как сортировка слиянием или пирамидальная сортировка . Когда входные данные имеют длину $n$, они образуют $n^{2}$ пар, и время на сортировку пар таким образом равно $O(n^{2}\log n)$. С точки зрения обозначения большого О , этот метод является самым быстрым из известных алгоритмов для $X+Y$ сортировка. Существует ли более быстрый алгоритм — открытая проблема . поставлен Элвином Берлекэмпом до 1975 года.

Вариант проблемы сортирует sumset , набор сумм пар, при этом повторяющиеся суммы сводятся к одному значению. Для этого варианта размер суммы может быть значительно меньше, чем $n^{2}$и чувствительные к выходу алгоритмы его построения. исследованы

Приложения

Стивен Скиена рассказывает о практическом применении минимизации тарифов на транзит , примере задачи о кратчайшем пути : найти самый дешевый билет на самолет с двумя перелетами между двумя заданными городами, используя входные данные, которые описывают как стоимость каждого перелета, так и возможные пары перелетов. объединены в один билет. Решение Скиены состоит в сортировке пар переходов по их общей стоимости в качестве примера $X+Y$ проблема сортировки, а затем тестирование полученных пар в этом отсортированном порядке до тех пор, пока не будет найдена разрешенная пара. Чтобы сгенерировать отсортированные пары в этом порядке, Скиена использует приоритетную очередь пар, первоначально содержащую только одну пару, состоящую из двух самых дешевых прыжков. Затем, когда пара $(x,y)$ удаляется из очереди и оказывается запрещенным, добавляются еще две пары, причем одна из этих двух пар объединяется $x$ со следующим прыжком после $y$ в отсортированном списке переходов к месту назначения, а другая пара, объединяющая $y$ со следующим прыжком после $x$ в отсортированном списке прыжков с самого начала. Таким образом, каждая последующая пара может быть найдена за логарифмическое время, и сортировать нужно только пары до первой допустимой.

$X+Y$ Сортировка — самая дорогая подпрограмма в алгоритме решения задачи проектирования СБИС , в которой необходимо разместить два субблока схемы СБИС бок о бок вдоль канала связи, чтобы минимизировать ширину канала, необходимую для маршрутизации пар провода от одного субблока к другому. Поскольку один субблок постоянно смещается относительно другого, ширина канала изменяется только в дискретных положениях, где концы двух проводов совпадают друг с другом, и нахождение отсортированного порядка этих положений для вычисления последовательности изменений ширины может быть выполнено $X+Y$ сортировка. Если бы эту задачу сортировки можно было ускорить, это также ускорило бы и задачу проектирования СБИС.

Другое приложение включает в себя полиномиальное умножение полиномов от одной переменной, которые могут иметь гораздо меньше членов, чем их степени . Произведение двух многочленов можно выразить как сумму произведений пар членов, по одному из каждого многочлена, и размещение этих почленных произведений в порядке степеней равносильно их сортировке по сумме степеней. Например, экземпляр $X+Y$ сортировка с $n=3$ приведенный выше пример соответствует умножению двух трехчленных многочленов для получения девятичленного многочлена: $${\begin{aligned}(&x+x^{2}+x^{9})(1+x^{4}+x^{9})\\&=x+x^{2}+x^{5}+x^{6}+x^{9}+x^{10}+x^{11}+x^{13}+x^{18}.\\\end{aligned}}$$ Степени всегда являются целыми числами, поэтому алгоритмы на основе целых чисел $X+Y$ может применяться сортировка. Однако для полиномов, количество членов которых сопоставимо с их степенью, алгоритмы полиномиального умножения на основе БПФ могут быть значительно более эффективными, чем почленное умножение.

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

Хорошо известная нижняя граница неструктурированной сортировки в модели дерева решений основана на факториальном числе отсортированных порядков, которое может иметь неструктурированный список. Поскольку каждое сравнение может в лучшем случае уменьшить количество возможных упорядочений в два раза, сортировка требует количества сравнений, по крайней мере равного двоичному логарифму факториала, который равен $n\log _{2}n-O(n)$. Ранняя работа над $X+Y$ сортировка использовала аналогичный подход, задавая вопрос, сколько различных отсортированных порядков возможно для этой задачи, и доказывая, что это число не более $O(n^{8n})$. Однако, поскольку его двоичный логарифм не более $8n\log _{2}n+O(1)$, что намного меньше известных временных границ для $X+Y$ сортировки, этот метод может привести только к слабым нижним оценкам числа сравнений.

Доказательство этой оценки относится $X+Y$ сортировка по сложности расположения гиперплоскостей в многомерной геометрии. Две входные коллекции для $X+Y$ проблема сортировки включает в себя $2n$ числа, которые альтернативно можно интерпретировать как декартовы координаты точки в $2n$-мерное пространство $\mathbb {R} ^{2n}$. Это пространство можно разделить на ячейки, так что в одной ячейке все точки соответствуют входным данным, которые обеспечивают одинаковый порядок сортировки. Для этого подразделения каждая граница между двумя ячейками лежит внутри гиперплоскости, определяемой равенством пар $x_{i}+y_{j}=x_{k}+y_{\ell }$, где $(x_{i},y_{j})$ и $(x_{k},y_{\ell })$ две пары, порядок которых меняется от одной соседней ячейки к другой. Эти гиперплоскости либо порождены двумя непересекающимися парами, либо имеют упрощенный вид $x_{i}=x_{k}$ или $y_{j}=y_{\ell }$, поэтому количество различных гиперплоскостей, которые можно определить таким образом, равно $$k=2{\binom {n}{2}}^{2}+2{\binom {n}{2}}.$$ Количество ячеек, на которое данное количество гиперплоскостей может разделить пространство размерности $2n$ в это $${\binom {k}{2n}}+{\binom {k}{2n-1}}+\cdots +{\binom {k}{0}}=O(n^{8n}).$$ Следовательно, набор $X+Y$ имеет $O(n^{8n})$ различные возможные отсортированные порядки.

Подобный стиль анализа оказался более успешным в исключении быстрых решений определенных обобщений $X+Y$ сортировку, показывая, что у них слишком много заказов, чтобы их можно было быстро отсортировать. В частности, Харпер и др. (1975) предлагают отдельно сортировать $X$ и $Y$, а затем построим двумерную матрицу значений $X+Y$ которые сортируются как по строкам, так и по столбцам, прежде чем использовать эти частично отсортированные данные для завершения сортировки $X+Y$. Эта идея использования матрицы с сортировкой по строкам и по столбцам лежит в основе метода, использованного Скиеной в транспортном приложении: и это может уменьшить количество сравнений на постоянный коэффициент по сравнению с наивной сортировкой сравнения. Однако для матриц, строки и столбцы которых отсортированы таким образом, количество возможных отсортированных упорядочений всей матрицы намного больше, чем $O(n^{8n})$настолько велик, что любой алгоритм сортировки сравнением, который может работать для произвольных $n\times n$ матрицы, отсортированные по строкам и столбцам, по-прежнему требуют $\Omega (n^{2}\log n)$ сравнения. Следовательно, если $X+Y$ проблема сортировки должна быть решена быстро, для решения необходимо использовать дополнительная информация о наборе $X+Y$ за пределами этого матричного порядка.

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

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

Первый явный алгоритм, который достигает обоих $O(n^{2})$ сравнения и $O(n^{2}\log n)$ через шестнадцать лет после Фредмана «Тотальная сложность» была опубликована Ламбертом (1992) . Алгоритм выполняет следующие шаги:

1. Рекурсивно отсортировать два набора $X+X$ и $Y+Y$.
2. Используйте эквивалентность $x_{i}-x_{j}\leq x_{k}-x_{\ell }\Leftrightarrow x_{i}+x_{\ell }\leq x_{j}+x_{k}$ вывести отсортированный порядок $X-X$ и $Y-Y$ без дополнительных сравнений.
3. Объедините два набора $X-X$ и $Y-Y$ в единый отсортированный порядок, используя ряд сравнений, линейных по их общему размеру.
4. Используйте объединенный порядок и эквивалентность $x_{i}+y_{j}\leq x_{k}+y_{\ell }\Leftrightarrow x_{i}-x_{k}\leq y_{\ell }-y_{j}$ вывести отсортированный порядок $X+Y$ без дополнительных сравнений.

Часть алгоритма, которая рекурсивно сортирует $X+X$ (или эквивалентно $Y+Y$) делает это, выполнив следующие действия:

1. Расколоть $X$ на два равных подсписка $A$ и $B$.
2. Рекурсивная сортировка $A+A$ и $B+B$
3. Сделайте вывод о порядке $A+B$ используя только сравнения с одного шага слияния, как указано выше.
4. Объединить отсортированные результаты $A+A$, $B+B$, и $A+B$ вместе.

Количество сравнений $C(n)$ необходимо для выполнения этого рекурсивного алгоритма на входе $n$ элементы можно анализировать с помощью рекуррентного соотношения $$C(n)\leq 2C(n/2)+O(n^{2}),$$ где $2C(n/2)$ термин повторения подсчитывает количество сравнений в рекурсивных вызовах алгоритма сортировки $A+A$ и $B+B$и $O(n^{2})$ term подсчитывает количество сравнений, использованных для объединения результатов. Основная теорема для рекуррентных соотношений такого вида показывает, что $C(n)=O(n^{2}).$ Общая временная сложность медленнее, $O(n^{2}\log n)$, поскольку этапы алгоритма используют уже выполненные сравнения для определения порядка других наборов. Эти шаги можно выполнить вовремя $O(n^{2}\log n)$ с использованием стандартного алгоритма сравнения-сортировки, в котором этапы сравнения заменены заявленными выводами.

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

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

Точно так же, как сортировка целых чисел может быть быстрее, чем сортировка сравнения для достаточно маленьких целых чисел, то же самое верно и для $X+Y$ сортировка. В частности, с целочисленными входами в диапазоне от $0$ до некоторого верхнего предела $M$, проблема может быть решена в $O(n+M\log M)$ операции с помощью быстрого преобразования Фурье .

Связанные проблемы

Некоторые другие задачи вычислительной геометрии имеют эквивалентную или более высокую сложность $X+Y$ сортировка, включающая построение сумм Минковского лестничных многоугольников, нахождение точек пересечения расположения линий в отсортированном порядке по их $x$-координаты, перечисление пар точек в порядке, отсортированном по их расстояниям, и проверка возможности одного прямолинейного многоугольника в другой. перевода

Задача проверки того, являются ли две пары в $X+Y$ Проблема сортировки равных сумм может быть решена путем сортировки пар, а затем проверки последовательных пар на равенство. В свою очередь, его можно использовать для решения задачи 3SUM , а это означает, что у него вряд ли будет строго субквадратичный алгоритм.