Distinção de elementos em O (n) tempo?

Todos sabemos que a distinção de elementos no modelo baseado em comparação não pode ser feita em tempo. No entanto, em uma palavra RAM, é possível alcançar melhor.$o(n\log n)$

Obviamente, se alguém assume a existência de uma função de hash perfeita que pode ser calculada em tempo linear, obtemos um algoritmo de tempo linear para a distinção de elementos: continue fazendo hashing dos números um por um e retorne 1 se houver uma colisão.

No entanto, existem dois problemas: 1) a maioria das construções de funções hash perfeitas que eu poderia encontrar aleatoriedade usada e 2) não consigo encontrar uma discussão sobre o tempo de pré-processamento em qualquer lugar, ou seja, o tempo necessário para decidir qual função hash será executada para usar com base no conjunto de números de entrada.

Fredman et al., " Armazenando uma tabela esparsa com pior caso de acesso$O(1)$ ", resolve o primeiro problema, fornecendo uma função hash com tempo de acesso no pior caso, mas não diz nada sobre o segundo problema. .$O(1)$

Então, para resumir, aqui está o que eu quero:

Projete um algoritmo que forneça um conjunto de números (cada número com bits) em uma palavra RAM com comprimento , encontre uma função de hash em tempo, onde . A função deve ter a propriedade de que, para qualquer , o número de elementos de que mapeiam é uma constante e a computação deve levar$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)$tempo em um modelo de palavra-RAM "razoável", ou seja, o modelo não deve permitir que funções "exóticas" nas palavras sejam avaliadas no tempo .$O(1)$

Também gostaria de saber se existem algoritmos para resolver a distinção de elementos na palavra RAM que não usam funções hash.

A distinção de elementos pode ser resolvida deterministicamente no modelo de RAM no tempo dentro de :$O(n\log\log n)\subset o(n\log n)$

Classifique no tempo em seu n número de bits w usando o algoritmo de classificação descrito por Han no STOC 2002 ("Classificação determinística em O ( n log log n ) no tempo e no espaço linear"), depois faça a varredura linear tempo para colisões.$O(n\log\log n)$$n$$w$$O(n\log\log n)$

Até onde eu sei, esse é o melhor resultado conhecido até hoje.

É exatamente isso que o documento FKS que você menciona faz - e leva tempo linear (na expectativa). Consulte a página 5 aqui para a análise ... http://www1.icsi.berkeley.edu/~luby/PAPERS/pairwise.ps