L'unicité d'un élément peut-elle être résolue en temps linéaire déterministe?

9

Considérez le problème suivant:

Entrée : liste des entiers $X,Y$

Objectif : déterminer s'il existe un entier qui figure dans les deux listes. $x$

Supposons que les deux listes soient de taille . Existe-t-il un algorithme déterministe à temps linéaire pour ce problème? En d'autres termes, pouvez-vous résoudre ce problème en temps déterministe, sans utiliser le hasard? $X,Y$ $n$ $O(n)$

Malheureusement, vous ne pouvez pas supposer que les éléments de la liste sont tous petits.

Je peux voir comment le résoudre dans le temps prévu utilisant un algorithme aléatoire: choisissez au hasard une fonction de hachage 2 universelle , stockez les éléments de dans une table de hachage (en utilisant comme fonction de hachage), puis recherchez chaque élément de pour voir s'il est dans la table de hachage. Le temps d'exécution prévu sera . Cependant, je ne vois pas comment trouver un algorithme déterministe avec un temps d'exécution . Si vous essayez de dérandomiser cela et de corriger une seule fonction de hachage spécifique, il existera une entrée dans le pire des cas qui entraînera l'exécution de cette procédure dans $O(n)$ $h$ $X$ $h$ $Y$ $O(n)$ $O(n)$ $\Theta(n^2)$ temps. Le meilleur algorithme déterministe que je puisse trouver consiste à trier les valeurs, mais ce ne sera pas du temps linéaire. Pouvons-nous atteindre un temps de fonctionnement linéaire?

De plus, je peux voir comment le résoudre en temps linéaire si vous supposez que tous les éléments de la liste sont des entiers dans la plage (en gros, trier le comptage) - mais je suis intéressé par ce qui se passe en général cas où nous ne pouvons pas supposer cela. $[1,n]$

Si la réponse dépend du modèle de calcul, le modèle RAM me vient à l'esprit, mais je serais intéressé par les résultats de tout modèle de calcul raisonnable. Je connais les limites inférieures de pour les algorithmes d'arbre de décision pour l'unicité des éléments , mais ce n'est pas définitif, car parfois nous pouvons trouver des algorithmes à temps linéaire même lorsqu'il existe un lié dans le modèle d'arbre de décision. $\Omega(n \log n)$ $\Omega(n \log n)$

Les tables de hachage sont O (n log n) car vous devez gérer les collisions.

Thorbjørn Ravn Andersen

1

@ ThorbjørnRavnAndersen, je ne vois pas d'où vous tenez cela. L'utilisation de 2 fonctions de hachage universelles et d'une table de hachage de taille appropriée garantit que le nombre de collisions de hachage est minime (avec une forte probabilité), donc je pense que le temps d'exécution

est réalisable. Je ne sais pas d'où vous venez

; si vous ne faites pas quelque chose de spécial (comme utiliser le hachage 2-universel), le pire des cas est , en raison de collisions.

O (n)

$O(n)$

O (n \lg n)

$O(n \lg n)$

O (n^{2})

$O(n^2)$

DW

Le diable est dans le détail, ici une "table de hachage de taille appropriée". Cela peut s'avérer assez important si vous ne voulez pas de collisions. Le n-log-n typique est (si je me souviens bien) pour gérer les collisions de la fonction de hachage avec une liste.

Thorbjørn Ravn Andersen

1

@ ThorbjørnRavnAndersen Le nombre attendu de clés mappées à la même adresse est constant (pour les tables qui ne sont pas surchargées), donc le type de résolution de collision n'a pas d'importance. Voir aussi ici . correspond au pire des cas si vous utilisez des BST équilibrés (externes) au lieu de listes.

O (n \log n)

$O(n \log n)$

Raphael

1

Vous pouvez résoudre le problème en temps linéaire si vous avez suffisamment de mémoire pour avoir un bit pour chaque valeur possible dans X et Y. Cela n'impose aucune restriction de l'ordre de X et Y.

Initialement, tous les bits ne sont pas définis.
Itérer sur X en définissant le bit correspondant.
Itérer sur Y en vérifiant si le bit correspondant a été défini ci-dessus.

Thorbjørn Ravn Andersen
la source

2

Malheureusement, vous ne pouvez pas supposer que tous les entiers sont petits (vous ne pouvez pas supposer qu'ils sont suffisamment petits pour que cet algorithme fonctionne). Dans le cas général, le temps d'exécution de cet algorithme sera exponentiel dans la longueur en bits des éléments de la liste. Merci quand même!

DW

Appelons-le alors un "tableau de bits de taille appropriée". Également linéaire dans la longueur de bit est équivalent à log-n. Souhaitez-vous vraiment obtenir des performances de connexion sans restrictions ni conditions préalables sur les données d'entrée?

Thorbjørn Ravn Andersen

2

@ ThorbjørnRavnAndersen L'espace est exponentiel dans la longueur de bit (vous devez mapper à partir de toutes les valeurs possibles), et le temps est linéaire dans la taille totale de la liste (vous devez regarder toutes les valeurs dans les deux listes). Rien n'est linéaire dans la longueur de bit.

wchargin

0

Puisque vous dites que les deux listes contiennent des entiers, je suppose que nous pouvons exécuter un tri radix sur les deux listes, puis faire une recherche linéaire en comparant les deux listes pour des éléments équivalents.

anirudh
la source

4

Cela ne fonctionne que s'il y a une limite sur l'amplitude des nombres.

Luke Mathieson

mais je pensais que la magnitude élevée ne sera un problème que pour le tri du comptage et pour le tri radix, nous pouvons sélectionner un radix suffisamment élevé pour résoudre ce problème ... s'il vous plaît laissez-moi savoir ce qui me manque ici

anirudh

Et si l'un des nombres est 2 ^ (2 ^ 128)?

miniBill

@anirudh mais vous avez alors un algorithme différent pour différentes tailles d'entrée - vous avez besoin d'un alphabet plus grand à chaque fois que vous augmentez le radix, vous exportez simplement la complexité de l'augmentation de l'amplitude pour augmenter la taille de l'alphabet. Bien sûr, cela n'est possible qu'en théorie également, je ne pense pas que beaucoup de matériel vous permette de changer la base dans laquelle il représente les nombres (nous pouvons faire semblant aux extrémités d'entrée et de sortie, mais cela se résume à (principalement) binaire ).

Luke Mathieson

0

Pourquoi ne pas insérer les entiers de chaque liste dans un simple tri au niveau du bit? Ne serait-ce pas optimal, dans le sens où il s'agit de , où est la taille moyenne des bits des entiers; en particulier, je ne vois pas comment vous pouvez faire mieux, car simplement * la lecture * des deux listes prendrait ce temps. $\mathcal O\left(n\cdot \overline m\right)$ $\overline m$

Realz Slaw
la source

Merci pour votre note. Voir le dernier paragraphe de la question, qui traite de ce point. Dans le modèle RAM, vous pouvez lire les deux listes en temps

- cela ne prend pas le temps

. C'est donc là que le modèle de calcul entre en jeu - cette réponse ne prouve pas réellement que le temps linéaire déterministe est impossible.

O (n)

$O(n)$

O (n \cdot \overbar m)

$O(n \cdot \overbar{m})$

DW

w

$w$

m

$m$

\bar{m}

$\overline{m}$

O (n)

$\mathcal O\left(n\right)$

w

$w$

w

$w$

n

$n$

m

$m$

n

$n$

n^{m}

$n^m$

-1

$O(n\log n)$

Omer Gold
la source

1

La question est assez explicite sur le temps déterministe linéaire, et non log-linéaire. De plus, pour déterminer si (et non sur quelle valeur) l'ensemble n'a que des éléments uniques, vous pouvez le faire plus rapidement que loglinear.

Evil

1

Ω (n \log n)

$\Omega(n\log n)$

1

Ω (n \log n)

$\Omega(n \log n)$

Ω (n \log n)

$\Omega(n \log n)$

O (n \log \log n)

$O(n \log \log n)$

O (n \log n)

$O(n \log n)$

Ω (n \log n)

$\Omega(n \log n)$

L'unicité d'un élément peut-elle être résolue en temps linéaire déterministe?

Réponses: