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. $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?

algorithms reference-request sorting Albert Hendriks
źródło

FWIW podejście probabilistyczne miesza się z funkcją skrótu niezależną od kolejności. Carter i Wegman napisali na ten temat jeden z oryginalnych artykułów ( sciencedirect.com/science/article/pii/0022000081900337 ), ale w cytatach tego artykułu nie widziałem niczego, co sugerowałoby algorytm deterministyczny (jak dotąd).

KWillets,

Cytowane przez ciebie stwierdzenie dotyczy modelu maszyny Turinga, który ma jedynie teoretyczne znaczenie. Algorytmy są zwykle analizowane w odniesieniu do modelu pamięci RAM.

Yuval Filmus

ah, to jest model, którego szukam. Poprawiłem pytanie.

Albert Hendriks,

Dlaczego po prostu nie zsumujesz pozycji w tablicy, a następnie nie porównasz sumy? Jeśli chodzi o twój tytuł, jest liniowy i odpowiada na pytanie „czy jedna tablica jest posortowaną wersją drugiej? „. Wiem, że to nie jest model maszyny Turinga, ale praktyczne rozwiązanie.

atayenel

@AlbertHendriks Ty (najprawdopodobniej) nie możesz posortować tablicy w na maszynie Turinga. Niektóre dolne granice SAT (np. Cs.cmu.edu/~ryanw/automated-lbs.pdf ) są w rzeczywistości dla maszyny RAM, przepraszam za mój mylący wcześniejszy komentarz.

O (n \log n)

$O(n\log n)$

Yuval Filmus

Odpowiedzi:

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 . $B$

{1, 2} \times {3, 4} \times \dots \times {2 n - 1, 2 n} .

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

i

$i$

2 i - 1

$2i-1$

2 i

$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 . $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 . $A$ $B$ $A$ $n!$ $\Omega(n\log n)$

Yuval Filmus
źródło

Wydawało mi się, że oznaczałoby to, że w ogóle, ale najwyraźniej model porównania jest inny.

P = Ω (n \log n)

$P = \Omega(n\log n)$

Albert Hendriks,

@AlbertHendriks, jest to ten sam model, który służy do pokazania dolnej granicy sortowania. Oznacza to, że jedyną operacją, którą możesz wykonać, jest porównanie, więc nie możesz zrobić lepiej. Myślę, że to odpowiada na twoje pytanie.

Kaveh

[Cntd] nie mamy silniejszych granic nawet przy sortowaniu! a jeśli możesz sortować szybciej niż n lg n, możesz użyć tego do rozwiązania problemu szybciej niż n lg n.

Kaveh

@AlbertHendriks, czy wiesz o liniowych algorytmach czasowych do sortowania liczb całkowitych? Sprawdź to w CLRS. Twoja sprawa może być jednym z przypadków, w których możemy sortować w czasie liniowym.

Kaveh

Liczby całkowite można sortować według (patrz nada.kth.se/~snilsson/fast-sorting ) lub w oczekiwanym czasie (patrz ieeexplore .ieee.org / stamp / stamp.jsp? arnumber = 1181890 ), a nawet w czasie liniowym, jeśli rozmiar słowa jest wystarczająco duży (patrz LNCS 8503, s. 26ff).

O (n \log \log n)

$O(n\log\log n)$

O (n \sqrt{\log \log n})

$O(n\sqrt{\log\log n})$

Yuval Filmus

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ść

\prod_{i = 1}^{n} (x - a_{i}) = \prod_{i = 1}^{n} (x - b_{i}) .

$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$

p

$p$

x_{0}

$x_0$

\prod_{i = 1}^{n} (x_{0} - a_{i}) \equiv \prod_{i = 1}^{n} (x_{0} - b_{i}) (\mod p) .

$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i})

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$

a_{i}, b_{i}

$a_i,b_i$

n^{O (1)}

$n^{O(1)}$

2^{n} n^{O (n)} = n^{O (n)}

$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)

$O(n)$

Ω (n)

$\Omega(n)$

n^{2}

$n^2$

p

$p$

n^{2}

$n^2$

p

$p$

1 - 1 / n

$1-1/n$

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i}) ≢ 0 (\mod p) .

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$

x_{0}

$x_0$

p

$p$

1 - n / p \geq 1 - 1 / n

$1-n/p \geq 1-1/n$

n

$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$

Yuval Filmus
źródło

Chociaż ten algorytm jest losowy, wyjaśnia, w jaki sposób zaimplementować pomysły w niektórych innych odpowiedziach, aby faktycznie działały. Ma również przewagę nad podejściem mieszającym: jest na miejscu.

Yuval Filmus

Myślę, że OP nie lubi algorytmów probabilistycznych, ponieważ nie podobał mu się algorytm oczekiwanego czasu liniowego wykorzystujący tablicę skrótów.

Kaveh

Kaveh masz rację. Ale oczywiście to rozwiązanie jest również interesujące i powinno zostać utrzymane, rozwiązuje problem algorytmów probabilistycznych. Myślę też, że wykorzystuje model, którego szukam.

Albert Hendriks

Zastanawiam się tylko, czy zapis O (1 / n) jest poprawny. Oczywiście wiem, co masz na myśli, ale myślę, że według definicji big-O jest to równoważne O (1).

Albert Hendriks,

Ani trochę. Jest to ilość ograniczona przez dla wystarczająco dużej liczby . To lepsza gwarancja niż .

C / n

$C/n$

n

$n$

O (1)

$O(1)$

Yuval Filmus

-3

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]$

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
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ć)
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$
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.

Nikos M.
źródło

Jeśli chodzi o zbieranie przedmiotów w odwrotnej kolejności do przebytej odległości, czy nie przekładałoby się to na porównania na poziomie wdrożenia i czy w tym momencie nie trzeba sortować „odległości”?

JustAnotherSoul