Sortowanie X + Y

Nierozwiązany problem w informatyce :

Czy istnieje algorytm sortowania szybszy niż ${\ Displaystyle O (n ^ {2} \$$n$ log

(więcej nierozwiązanych problemów w informatyce)

$_$ wizualizacja . Zbiory wejściowe i ${\ displaystyle$$Y} są reprezentowane przez zestawy pionowych i poziomych czarnych linii (odpowiednio), a celem problemu$ posortowanie punktów przecięcia według pozycji czerwonej przekątnej linie przez nie.

W informatyce $sortowanie$ to problem par liczb sum . Zastosowania problemu obejmują minimalizację opłat tranzytowych , projektowanie VLSI i rzadkie mnożenie wielomianów. Podobnie jak w przypadku sortowania porównawczego i sortowania liczb całkowitych bardziej ogólnie, algorytmy dla tego problemu mogą opierać się tylko na porównaniach tych sum lub na innych operacjach, które działają tylko wtedy, gdy dane wejściowe są małymi liczbami całkowitymi.

Nie wiadomo, czy ten problem ma rozwiązanie oparte na porównaniach, którego czas działania jest asymptotycznie szybszy niż sortowanie nieustrukturyzowanej listy równie wielu elementów. Dlatego badania nad tym problemem koncentrowały się na dwóch podejściach do rozstrzygnięcia kwestii, czy taka poprawa jest możliwa: opracowaniu algorytmów, które ulepszają nieustrukturyzowane sortowanie pod względem liczby porównań, a nie całkowitego czasu działania, oraz dolnych granic dla liczba porównań opartych na zliczaniu komórek w podpodziałach przestrzeni wielowymiarowych. Oba podejścia są ze sobą historycznie powiązane, ponieważ pierwsze algorytmy, które wykorzystywały niewiele porównań, opierały się na słabości dolnych granic liczenia komórek.

Opis problemu i historia

Dane wejściowe do $się$$sortowania$ z dwóch skończonych $długości$ liczb i o samej $par$ problemu jest zbiór wszystkich liczby z $Y$ liczby z , ułożonych w porządku posortowanym według sumy każdej pary. Jako mały przykład, dla wejść ${\ Displaystyle X = \ {1,2,9 \}}$ i ${\ Displaystyle Y = \ {0,4,9 \}}$ , wyjście powinno być lista par

$${\ Displaystyle (1,0), \, (2,0), \, (1,4), \, (2,4), \, (9,0), \, (1,9), \ ,(2,9),\,(9,4),\,(9,9)}$$

jednego elementu z i jednego elementu z , wymienionych w kolejności $posortowanej$ według sumy par $\ displaystyle X}$

$${\ Displaystyle 1,2,5,6,9,10,11,13,18.}$$

Jednym ze sposobów rozwiązania tego problemu byłoby skonstruowanie par do sortowania ( iloczyn kartezjański dwóch kolekcji) i użycie tych par jako danych wejściowych do standardowego algorytmu sortowania porównawczego , takiego jak sortowanie przez scalanie lub sortowanie na stosie . Gdy dane wejściowe mają długość $($ tworzą $displaystyle O (n^{2}\log n)}$ a czas na posortowanie par w ten sposób to $O$ . Pod względem $ta$ O jest najszybszym znanym algorytmem sortowania To, czy istnieje szybszy algorytm, jest otwartym problemem , postawionym przez Elwyna Berlekampa przed 1975 rokiem.

Wariant problemu sortuje sumset , zbiór sum par, ze zduplikowanymi sumami skondensowanymi do jednej wartości. $W$ przypadku tego wariantu rozmiar sumsetu może być znacznie mniejszy niż zbadano jego konstruowania wrażliwe na dane wyjściowe.

Aplikacje

Steven Skiena opowiada o praktycznym zastosowaniu w minimalizacji opłat tranzytowych , przykładzie problemu najkrótszej ścieżki : znajdź najtańszy bilet lotniczy z dwoma przeskokami między dwoma danymi miastami, na podstawie danych wejściowych opisujących zarówno koszt każdego przeskoku, jak i pary przeskoków, które mogą być połączone w jeden bilet. Rozwiązanie Skieny polega na sortowaniu par chmielu według ich całkowitego kosztu jako przykład ${\ displaystyle X + Y}$ problem z sortowaniem, a następnie testowanie powstałych par w tej posortowanej kolejności, aż do znalezienia takiej, która jest dozwolona. Aby wygenerować posortowane pary w tej kolejności, Skiena używa priorytetowej kolejki par, początkowo zawierającej tylko jedną parę, składającą się z dwóch najtańszych przeskoków. Następnie, gdy para ${$ i uznana za niedozwoloną, dodawane są jeszcze dwie pary, przy czym jedna z tych dwóch par łączy x $}$ następny przeskok po ${\ displaystyle y}$ na posortowanej liście przeskoków do miejsca docelowego, a druga para łączy się z następnym przeskokiem po na $posortowanej$ liście przeskoków $od$ W ten sposób każdą kolejną parę można znaleźć w czasie logarytmicznym i należy posortować tylko pary do pierwszej dopuszczalnej.

Sortowanie jest najdroższą procedurą algorytmu dla problemu w $zminimalizować$ VLSI , w należy umieścić dwie podjednostki obwodu VLSI obok siebie wzdłuż kanału komunikacyjnego, szerokość kanału potrzebna do poprowadzenia par przewodów z jednej podjednostki do drugiej. Ponieważ jedna podjednostka jest w sposób ciągły przesuwana względem drugiej, szerokość kanału zmienia się tylko w dyskretnych pozycjach, w których końce dwóch drutów pokrywają się ze sobą, i znalezienie posortowanej kolejności tych pozycji w celu obliczenia sekwencji zmian szerokości może być wykonany przez ${\ Displaystyle X + Y}$ . Gdyby można było przyspieszyć ten problem z sortowaniem, przyspieszyłoby to również zadanie projektowania VLSI.

Inne zastosowanie obejmuje mnożenie wielomianów dla wielomianów pojedynczej zmiennej, które mogą mieć o wiele mniej wyrazów niż ich stopnie . Iloczyn dwóch wielomianów można wyrazić jako sumę iloczynów par wyrazów, po jednym z każdego wielomianu, a umieszczenie tych iloczynów wyraz po wyrazie w porządku stopniowym jest równoznaczne z posortowaniem ich według sumy stopni. $}$ przypadek sortowania z podanym jako przykład powyżej odpowiada mnożeniu dwóch ${\ displaystyle X$ wielomiany trójczłonowe , aby uzyskać wielomian dziewięcioczłonowy:

$${\ Displaystyle {\ rozpocząć {wyrównane} (& 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}.\\\koniec{wyrównany} }}$$

Stopnie są zawsze liczbami całkowitymi, więc można zastosować algorytmy oparte na $do$ całkowitych Jednak w przypadku wielomianów, których liczba wyrazów jest porównywalna z ich stopniem, algorytmy mnożenia wielomianów oparte na FFT mogą być znacznie bardziej wydajne niż mnożenie wyraz po wyrazie.

Liczba zamówień

Dobrze znana dolna granica sortowania nieustrukturyzowanego w modelu drzewa decyzyjnego jest oparta na silni liczby posortowanych rzędów, które może mieć lista nieustrukturyzowana. Ponieważ każde porównanie może co najwyżej zmniejszyć liczbę możliwych porządków o współczynnik dwa, sortowanie wymaga liczby porównań co najmniej równej logarytmowi binarnemu silni , czyli ${\ Displaystyle n\log _{2}nO(n)}$ . Wczesne prace nad ${\ displaystyle X + Y}$ sortowanie przebiegało w podobny sposób, pytając, ile różnych uporządkowań posortowanych jest możliwych dla tego problemu i udowadniając, że liczba ta wynosi co najwyżej ${\ Displaystyle O (n ^ {8n}) }$ . $granice$ najwyżej $\displaystyle X+Y}$ niż znane $czasowe$ sortowania, ta metoda może prowadzić jedynie do słabych dolnych granic liczby porównań.

Dowód tego powiązania dotyczy $ze$ układu hiperpłaszczyzn geometrii wielowymiarowej. Dwa zbiory wejściowe dla $displaystyle 2n}$$sortowania$ obejmują $liczby ,$ jako współrzędne kartezjańskie punktu w - 2 przestrzeń wymiarowa ${\ Displaystyle \ mathbb {R} ^ {2n}}$ . Przestrzeń tę można podzielić na komórki, tak aby w obrębie pojedynczej komórki wszystkie punkty odpowiadały danym wejściowym, które tworzą ten sam posortowany porządek. W przypadku tego podziału każda granica między dwiema komórkami leży w hiperpłaszczyźnie określonej przez równość par ${\ Displaystyle x_ {i} + y_ {j} = x_ {k} + y_ { \ ell}}$ , gdzie ${\ Displaystyle (x_ {i}, y_ {j})}$ i ${\ Displaystyle (x_ {k}, y_ {\ ell})}$ to dwie pary, których kolejność zmienia się z jednej sąsiedniej komórki do drugiej. Te hiperpłaszczyzny $y$$\ell }}$ pary, albo mają uproszczone formy lub $y_ {j} =$ , więc liczba odrębnych hiperpłaszczyzn, które można określić w ten sposób, wynosi

$${\ Displaystyle k = 2 {\ binom {n} {2}} ^ {2} + 2 {\ binom {n} {2}}.}$$

Liczba komórek, na które ta liczba hiperpłaszczyzn może podzielić przestrzeń o wymiarze, wynosi ${\ displaystyle 2n}$

$${\ Displaystyle {\ binom {k} {2n}} + {\ binom {k} {2n-1}} + \ cdots + {\ binom {k} {0}} = O (n ^ {8n}). }$$

Dlatego zbiór $.$$_$ _

Podobny styl analizy był bardziej skuteczny w wykluczaniu szybkich rozwiązań pewnych uogólnień $,$ pokazując, że mają zbyt wiele uporządkowań, aby można je było szybko W szczególności Harper i in. (1975) sugerują oddzielne sortowanie i ${\$$displaystyle Y}$ , a następnie skonstruowanie dwuwymiarowej macierzy wartości ${\ displaystyle X + Y$$według wierszy, jak i kolumn przed użyciem tych$ posortowanych danych do zakończenia sortowania . Ten pomysł użycia macierzy posortowanej według wierszy i kolumn stanowi podstawę metody stosowanej przez Skiena w aplikacji transportowej i może zmniejszyć liczbę porównań o stały współczynnik w stosunku do naiwnego sortowania porównań. Jednak dla macierzy, których wiersze i kolumny są posortowane w ten sposób, liczba możliwych uporządkowań całej macierzy jest znacznie większa niż $wymaga$${8n})}$ , tak duży, że każdy algorytm sortowania porównawczego, który może działać dla dowolnych według wierszy i kolumn, nadal ${\ Displaystyle \ Omega (n ^ {2} \ log n)}$ porównania. Dlatego jeśli problem sortowania ma zostać szybko rozwiązany, rozwiązanie musi wykorzystywać dodatkowe informacje o zbiorze ${\ displaystyle X$${\ Displaystyle X + Y}$ poza tym uporządkowaniem macierzy.

Liczba porównań

W przypadku klasycznego problemu sortowania porównań czas sortowania i liczba porównań potrzebnych do sortowania mieszczą się w stałych współczynnikach. Ale w przypadku $sortowania$$liczba$ porównań jest mniejsza niż najlepsza znana granica czasowa: w r., Że wykonać tylko przy użyciu ${\ Displaystyle O (n ^ {2})}$ porównania. Bardziej ogólnie, pokazał, że każdy zestaw ${\ displaystyle N} elementy, których posortowane$$uporządkowanie$ zostało już ograniczone do rodziny , można sortować za pomocą ${\ Displaystyle \ log _ {2} | \ Gamma | + O (N)}$ przez formę binarnego sortowania przez wstawianie . Dla ${\ Displaystyle X + Y}$ , ${\ Displaystyle N = n ^ {2}}$ , i ${\ Displaystyle |\ Gamma |= O (n ^ {8n})}$ , więc ${\ Displaystyle \ log _ {2} | \ Gamma | = O (n \ log n)}$ i granica Fredmana oznacza, że ​​tylko ${\ Displaystyle O (n ^ {2) })}$ potrzebne są porównania. Jednak w metodzie Fredmana czas potrzebny na podjęcie decyzji, które porównania wykonać, może być znacznie dłuższy niż granica liczby porównań.

Pierwszy jawny algorytm, który osiąga zarówno ${2} \$ , jak i sumę $) {\ Displaystyle$ ^ złożoność została opublikowana szesnaście lat po Fredmanie przez Lamberta (1992) . Algorytm wykonuje następujące kroki:

1. $displaystyle Y + Y$ posortuj dwa zestawy i $+$ }
2. $Displaystyle x_ {i} -x_ {j} \ równoważnik x_ {k} -x_ {\ ell} \Leftrightarrow x_ {i} + x_ {\ ell} \ równoważnik x_ {j} + x_ {k}}, aby$ ≤ wywnioskować posortowane uporządkowania ${\ Displaystyle XX}$ i ${\ Displaystyle YY}$ bez dodatkowych porównań .
3. Połącz dwa zestawy i $displaystyle$$YY}$ w jedną posortowaną kolejność, używając szeregu porównań liniowych w ich całkowitym
4. Użyj połączonej kolejności i równoważności ${\ Displaystyle x_ {i} + y_ {j} \ równoważnik x_ {k} + y_ {\ ell} \ Leftrightarrow x_ {i} -x_ {k} \ leq y_ {\ ell} -y_ {j}}, aby$ wywnioskować posortowaną kolejność ${\ Displaystyle X + Y}$ bez dodatkowych porównań.

Część algorytmu, która rekurencyjnie sortuje $displaystyle X + X}$ lub równoważnie $) robi to$ wykonując następujące kroki:

1. Podziel ${\ displaystyle X}$ na dwie równe listy podrzędne ${\ displaystyle A}$ i ${\ displaystyle B}$ .
2. Sortuj rekurencyjnie ${\ Displaystyle A + A}$ i ${\ Displaystyle B + B}$
3. Wywnioskuj o kolejności na $podstawie$ porównań z jednego etapu scalania, jak
4. $posortowane$ wyniki razem $_$ _ $_$ _

Liczbę porównań potrzebnych do wykonania tego $rekurencyjnego$ algorytmu na danych wejściowych elementów przeanalizować za pomocą rekurencji do $n}$

$${\ Displaystyle C (n) \ równoważnik 2C (n/2) + O (n ^ {2}),}$$

gdzie $2C ($ zlicza liczbę porównań w rekurencyjnych wywołaniach algorytmu sortowania i B ${\ Displaystyle$${\ displaystyle B + B}$$do$ a zlicza liczbę porównań użytych Twierdzenie mistrza dla relacji rekurencyjnych tej postaci pokazuje, ${\ Displaystyle C (n) = O (n ^ {2}).}$ Całkowita złożoność czasowa jest wolniejsza, ${\ Displaystyle O (n ^ {2} \ log n)}$ , ponieważ kroków algorytmu, które wykorzystują już wykonane porównania, aby wywnioskować uporządkowanie innych zbiorów. Te kroki można wykonać w czasie ${\ Displaystyle O (n ^ {2} \ log n)}$ przy użyciu standardowego algorytmu sortowania porównawczego, w którym kroki porównania zostały zastąpione podanymi wnioskami.

${2}$ ) { \ $Omega$$, ale przy bardziej ogólnych$ liczby elementów

Algorytmy nie oparte na porównaniach

Tak jak sortowanie liczb całkowitych $może$ liczb całkowitych, to samo dotyczy sortowania. W szczególności, przy wprowadzaniu liczb całkowitych $O (n + M \ log M)}$ zakresie od pewnej górnej granicy , problem można rozwiązać w $O$$)$ operacji za pomocą szybkiej transformaty Fouriera .

Powiązane problemy

Kilka innych problemów w geometrii obliczeniowej ma taką samą lub większą złożoność jak $sortowanie$ , w tym konstruowanie sum Minkowskiego wielokątów schodowych, znajdowanie punktów przecięcia układu w posortowanej kolejności według ich $displaystyle x} -$ współrzędne, wyświetlanie par punktów w kolejności posortowanej według ich odległości i sprawdzanie, czy jeden prostoliniowy wielokąt można przełożyć tak, aby pasował do innego.

Problem sprawdzania, czy dwie pary w $problemie sortowania mają równe sumy,$ rozwiązać, sortując pary, a następnie testując kolejne pary pod kątem Z kolei można go użyć do rozwiązania problemu 3SUM , co sugeruje, że jest mało prawdopodobne, aby miał silnie subkwadratowy algorytm.