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ąćn w w h : S → { 1 , … , m } O ( n ) m = O ( n ) h j ∈ { 1 , … , m } S $S$$n$$w$$w$$h:S\rightarrow \{1, \ldots , m\}$$O(n)$$m = O(n)$$h$$j \in \{1, \ldots , m\}$$S$$j$O ( 1 $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.

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 n liczb w bitów przy użyciu algorytmu sortowania opisanego przez Hana w STOC 2002 („Sortowanie deterministyczne w O ( n log log n ) 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ś.

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