Odróżnienie elementu w czasie O (n)?

Wszyscy wiemy, że odróżnienia elementów w modelu opartym na porównaniu nie można zrobić w czasie . Jednak na słownej pamięci RAM można osiągnąć lepiej. $o(n\log n)$

Oczywiście, jeśli przyjmie się istnienie idealnej funkcji skrótu, którą można obliczyć w czasie liniowym, otrzymamy liniowy algorytm czasu dla odróżnienia elementu: po prostu utrzymuj wartości mieszania jeden po drugim i zwracaj 1, jeśli występuje kolizja.

Istnieją jednak dwa problemy: 1) większość konstrukcji doskonałych funkcji skrótu, które mogłem znaleźć, wykorzystała losowość i 2) Nie mogę nigdzie znaleźć dyskusji na temat czasu wstępnego przetwarzania, tj. Czasu potrzebnego do podjęcia decyzji, którą funkcję skrótu wybierzesz używać na podstawie wejściowego zestawu liczb.

Fredman i wsp. „ Przechowywanie rzadkiej tabeli z czasem dostępu najgorszym przypadku $O(1)$ ” rozwiązuje pierwszy problem, zapewniając funkcję skrótu z czasem dostępu w najgorszym przypadku, ale nie mówi nic o drugim problemie . $O(1)$

Podsumowując, oto, czego chcę:

Zaprojektować algorytm danym zestawie z liczb (każda liczba jest bitów) na słowo-RAM o długości słowa , znajduje się funkcja mieszająca W czas, gdzie . Funkcja powinna mieć właściwość, że dla dowolnego liczba elementów odwzorowanych na jest stała, a obliczenie powinno przyjąć $S$ $n$ $w$ $w$ $h:S\rightarrow \{1, \ldots , m\}$ $O(n)$ $m = O(n)$ $h$ $j \in \{1, \ldots , m\}$ $S$ $j$ $h(i)$ $O(1)$ czas w „rozsądnym” słowie-modelu RAM, tzn. model nie powinien pozwalać na „egzotyczne” funkcje na słowach oceniane w czasie . $O(1)$

Chciałbym również wiedzieć, czy istnieją algorytmy rozwiązujące rozróżnienie elementów w słowie-RAM, które w ogóle nie używają funkcji skrótu.

ds.algorithms

— Vinayak Pathak
źródło

Re: „Chciałbym również wiedzieć, czy istnieją algorytmy do rozwiązywania rozróżnienia elementów w słowie-RAM, które w ogóle nie używają funkcji skrótu”. - tak długo, jak chcesz tylko a nie liniowy, jest wiele pracy nad sortowaniem słowa RAM (patrz en.wikipedia.org/wiki/Integer_sorting ). Niektóre z tych algorytmów używają haszowania, ale inne nie.

o (n \log n)

$o(n\log n)$

— David Eppstein

Czy dozwolone są przybliżone rozwiązania?

— AT

(Myślę, że) Twój proces myślenia pomija jeden krok: 1. Postulujesz, że najlepszą złożonością w modelu porównawczym jest 2. Pytasz, jak można to poprawić w modelu RAM 3. Ty bezpośrednio zapytaj o rozwiązanie w czasie w modelu pamięci RAM. Raczej powinieneś studiować rozwiązania w modelu RAM i sprawdzić, czy możesz je poprawić?

Θ (n \log n)

$\Theta(n\log n)$

O (n)

$O(n)$

o (n \log n)

$o(n\log n)$

— Jeremy

Czy Radix jest dla ciebie zbyt wolny?

— Thomas Mueller

Odróżnienie elementów można rozwiązać deterministycznie w modelu pamięci RAM w czasie w czasie : $O(n\log\log n)\subset o(n\log n)$

Sortuj w czasie w obrębie twoich liczb bitów przy użyciu algorytmu sortowania opisanego przez Hana w STOC 2002 („Sortowanie deterministyczne w przestrzeni i przestrzeni liniowej”), a następnie skanuj liniowo czas na kolizje. $O(n\log\log n)$ $n$ $w$ $O(n\log\log n)$

O ile mi wiadomo, jest to najlepszy wynik znany do dziś.

— Jeremy
źródło

To właśnie robi wspomniany papier FKS - i zajmuje to czas liniowy (w oczekiwaniu). Analiza znajduje się na stronie 5 ... http://www1.icsi.berkeley.edu/~luby/PAPERS/pairwise.ps

— Sariel Har-Peled
źródło