Distinction des éléments en temps O (n)?

Nous savons tous que la distinction des éléments dans le modèle basé sur la comparaison ne peut pas être effectuée en temps . Cependant, sur un mot-RAM, on peut éventuellement obtenir de meilleurs résultats.$o(n\log n)$

Bien sûr, si l'on suppose l'existence d'une fonction de hachage parfaite qui peut être calculée en temps linéaire, nous obtenons un algorithme de temps linéaire pour la distinction des éléments: continuez simplement à hacher les nombres un par un et retournez 1 en cas de collision.

Cependant, il y a deux problèmes: 1) la plupart des constructions de fonctions de hachage parfaites que j'ai pu trouver utilisées de manière aléatoire et 2) Je ne trouve nulle part une discussion sur le temps de prétraitement, c'est-à-dire le temps nécessaire pour décider quelle fonction de hachage on va à utiliser en fonction de l'ensemble de nombres entré.

Fredman et al. " Stockage d'une table clairsemée avec le temps d'accès pire des cas$O(1)$ " résout le premier problème en fournissant une fonction de hachage avec le temps d'accès dans le pire des cas, mais ne dit rien sur le deuxième problème .$O(1)$

Donc, pour résumer, voici ce que je veux:

Concevoir un algorithme qui donne un ensemble de n chiffres (chaque numéro étant w bits de long) sur un mot-RAM avec une longueur de mot w , trouve une fonction de hachage h : S → { 1 , ... , m } en O ( n ) du temps , où m = O ( n ) . La fonction h devrait avoir la propriété que pour tout j ∈ { 1 , … , m } , le nombre d'éléments de$S$$n$$w$$w$$h:S\rightarrow \{1, \ldots , m\}$$O(n)$$m = O(n)$$h$$j \in \{1, \ldots , m\}$ ce mappage vers j est une constanteet lecalcul de h ( i ) devrait prendre O ( 1 ) dans un modèle de mot-RAM "raisonnable", c'est-à-dire que le modèle ne devrait pas permettre aux fonctions "exotiques" des mots d'être évaluées dans O ( 1 ) le temps.$S$$j$$h(i)$$O(1)$$O(1)$

Je voudrais également savoir s'il existe des algorithmes pour résoudre la distinction des éléments sur le mot-RAM qui n'utilisent pas du tout de fonctions de hachage.

La distinction des éléments peut être résolue de manière déterministe dans le modèle RAM dans le temps en temps:$O(n\log\log n)\subset o(n\log n)$

Triez dans le temps dans vos n nombres de w bits en utilisant l'algorithme de tri décrit par Han dans STOC 2002 ("Tri déterministe dans O ( n log log n ) temps et espace linéaire"), puis scannez en linéaire le temps des collisions.$O(n\log\log n)$$n$$w$$O(n\log\log n)$

À ma connaissance, c'est le meilleur résultat connu à ce jour.

C'est exactement ce que fait le document FKS que vous mentionnez - et cela prend du temps linéaire (dans l'attente). Voir la page 5 ici pour l'analyse ... http://www1.icsi.berkeley.edu/~luby/PAPERS/pairwise.ps