Deterministyczny algorytm czasu liniowego do sprawdzania, czy jedna tablica jest posortowaną wersją drugiej

Rozważ następujący problem:

Dane wejściowe: dwie tablice i o długości , gdzie jest posortowane.B n $A$$B$$n$$B$

Pytanie: czy i zawierają te same elementy (z ich wielokrotnością)?$A$$B$

Jaki jest najszybszy algorytm deterministyczny dla tego problemu?
Czy można to rozwiązać szybciej niż ich sortowanie? Czy ten problem można rozwiązać w deterministycznym czasie liniowym?

Nie określiłeś modelu obliczeniowego, więc przyjmuję model porównawczy.

Rozważ szczególny przypadek, w którym tablica jest pobierana z listy Innymi słowy, tym elementem jest albo albo .{ 1 , 2 } × { 3 , 4 } × ⋯ × { 2 n - 1 , 2 n } . i 2 i - 1 2 $B$

$$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$$ $i$$2i-1$$2i$

Zastrzeżenia patentowe że jeśli algorytm stwierdzono, że i zawierają takie same elementy, że algorytm porównaniu każdy element jej odpowiednika w . Istotnie, przypuśćmy, że algorytm stwierdza, że i zawierają te same elementy, ale nie porównuje pierwszy element do swojego odpowiednika w . Jeśli zmienimy pierwszy element, algorytm działałby dokładnie w ten sam sposób, nawet jeśli odpowiedź jest inna. To pokazuje, że algorytm musi porównać pierwszy element (i żadnego innego elementu) do jego odpowiednika w .B B A A B B A $A$$B$$B$$A$$A$$B$$B$$A$$A$

Oznacza to, że i zawierają takie same elementy, a po stwierdzeniu, to algorytm wie posortowane kolejność . Dlatego musi mieć co najmniejróżne liście, więc zajmuje to czas .B A n ! Ω ( n log n $A$$B$$A$$n!$$\Omega(n\log n)$

Ta odpowiedź dotyczy innego modelu obliczeń: modelu pamięci RAM kosztu jednostkowego. W tym modelu słowa maszynowe mają rozmiar , a operacje na nich zajmują czas . Przyjmujemy również dla uproszczenia, że ​​każdy element tablicy mieści się w jednym słowie maszynowym (a więc ma co najwyżej wielkości).$O(\log n)$$O(1)$$n^{O(1)}$

Skonstruujemy losowy algorytm liniowy z jednostronnym błędem (algorytm może zadeklarować, że dwie tablice zawierają te same elementy, nawet jeśli tak nie jest), w celu trudniejszego ustalenia, czy dwie tablice i zawierają te same elementy. (Nie wymagamy sortowania żadnego z nich.) Nasz algorytm popełni błąd z prawdopodobieństwem co najwyżej .$a_1,\ldots,a_n$$b_1,\ldots,b_n$$1/n$

Chodzi o to, że następująca tożsamość utrzymuje, że tablice zawierają te same elementy: Dokładne obliczenie tych wielomianów zajmie zbyt dużo czasu. Zamiast tego wybieramy losową liczbę pierwszą i losową i testujemy, czy Jeśli tablice są równe, test zawsze się powiedzie, więc skoncentrujmy się na przypadkach, w których tablice są różne. W szczególności pewien współczynnik jest niezerowy. Ponieważ mają wielkość , współczynnik ten ma wielkośćpx0 n ∏ i = 1 (x0-ai)≡ n ∏ i = 1 (x0-bi

$$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$$ $p$$x_0$ $$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$$ a i , b i n O ( 1 ) 2 n n O ( n ) = n O ( n ) O ( n ) Ω ( n ) n 2 p $\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$$a_i,b_i$$n^{O(1)}$$2^n n^{O(n)} = n^{O(n)}$, a więc ma co najwyżej podstawowe czynniki wielkości . Oznacza to, że jeśli wybierzemy zestaw co najmniej liczb pierwszych o rozmiarze co najmniej (powiedzmy), to dla losowej liczby pierwszej tego zestawu będzie on z prawdopodobieństwem wynosić co najmniej że Przypadkowy modulo będzie świadkiem tego z prawdopodobieństwem (ponieważ wielomian stopnia co najwyżej ma co najwyżej pierwiastków).$O(n)$$\Omega(n)$$n^2$$p$$n^2$$p$$1-1/n$ $$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$$ $x_0$$p$$1-n/p \geq 1-1/n$$n$$n$

Podsumowując, jeśli wybierzemy losowe wielkości mniej więcej spośród zestawu co najmniej różnych liczb pierwszych i losowego modulo , to gdy tablice nie zawierają tych samych elementów, nasz test zakończy się niepowodzeniem z prawdopodobieństwem . Przeprowadzenie testu zajmuje czas ponieważ mieści się w stałej liczbie słów maszynowych.$p$$n^2$$n^2$$x_0$$p$$1-O(1/n)$$O(n)$$p$

Używając wielomianowego testowania pierwotności czasu, a ponieważ gęstość liczb pierwszych z grubsza wynosi , możemy wybrać losową liczbę pierwszą w czasie . Wybór losowy modulo mogą być realizowane na różne sposoby, a jest łatwiejsze, ponieważ w naszym przypadku nie musimy całkowicie jednolite losowo .$n^2$$\Omega(1/\log n)$$p$$(\log n)^{O(1)}$$x_0$$p$$x_0$

Podsumowując, nasz algorytm działa w czasie , zawsze zwraca TAK, jeśli tablice zawierają te same elementy, i zwraca NIE z prawdopodobieństwem jeśli tablice nie zawierają tych samych elementów. Można zwiększyć prawdopodobieństwo błędu do dla każdego stałego .$O(n)$$1-O(1/n)$$1-O(1/n^C)$$C$

zaproponuję inny algorytm (lub przynajmniej schemat takiego algorytmu)

Schemat zakłada, że ​​wartości (zakładane „ liczby całkowite ”) mieszczą się w (wąskim?) Zakresie między$[min,max]$

1. W czasie skanowania dwóch tablic, możemy znaleźć wartości i dla obu i ich wielokrotności, jeśli się różnią, tablice nie są wzajemnymi permutacjami$O(n)$minmax

2. Odejmij minwszystkie wartości z obu tablic (tutaj nie bierze się pod uwagę faktu, że jedna tablica jest już posortowana, prawdopodobnie można to poprawić)

3. Załóżmy, że wartości w tablicach reprezentują masy i do każdej wielkości stosujemy przyspieszenie / prędkość ( w niektórych przypadkach można to poprawić do wartości )$1$$c > 1$

4. przesuwać masy, aż osiągną maksymalną wartość max-min, ma to złożoność . Pozwala to na znalezienie zarówno tych samych wartości, jak i ich wielokrotności, jeśli się różnią, tablice nie są wzajemnymi permutacjami. W innym przypadku tablice są wzajemnymi permutacjami.$O((max-min)n)$

zauważ, że powyższy schemat algorytmu może być (deterministycznie) dość szybki w wielu praktycznych sytuacjach.

Powyższy schemat algorytmu jest odmianą algorytmu sortującego w czasie liniowym wykorzystującym „ ruchome masy ”. Fizyczna intuicja stojąca za algorytmem sortowania „ ruchomych mas ” jest następująca:

Załóżmy, że wartość każdego elementu faktycznie reprezentuje jego masę i wyobraź sobie, że układasz wszystkie przedmioty w linii i przykładasz taką samą siłę przyspieszenia.

Następnie każdy przedmiot przesunie się na odległość związaną z jego masą, bardziej masywny mniejszy dystans i odwrotnie. Następnie, aby odzyskać posortowane przedmioty, po prostu zbierz przedmioty w odwrotnej kolejności według przebytej odległości.

Algorytm ten jest liniowo-czasowy i deterministyczny , ale jest zastrzeżenie, że wielkość początkowej siły przyspieszenia i odległości do podróży (lub czasu oczekiwania) jest związana z rozkładem wartości (tj. „ Masami ”, współczynnik powyżej). Można także spróbować dyskretyzować miejsce, w którym przedmioty mogą podróżować do siatki i uzyskać stały współczynnik prędkości algorytmu (i użyć procedury szybkiego sortowania do sortowania różnych przedmiotów w tej samej komórce ).$max-min$

W związku z tym, powyższy algorytm jest podobne do algorytmów oparte sortowania (na przykład podstawa sortowania , zliczanie sortowania )

Można by pomyśleć, że ten algorytm może niewiele znaczyć, ale pokazuje przynajmniej jedną rzecz. To, że „ zasadniczo ”, na poziomie fizycznym, sortowanie dowolnych liczb jest operacją w czasie liniowym dla liczby elementów.