Calculer l'intersection en temps linéaire ?

Question

Existe-t-il un algorithme qui, compte tenu de deux ensembles, calcule leur intersection en temps linéaire ?

Je peux exécuter deux boucles for pour vérifier toutes les paires d'éléments, enregistrant les éléments que je trouve dans les deux ensembles. Cependant, le temps d'exécution sera 0(n²). Comment puis-je faire cela en temps O(n) ?

Answer 1

Je me demande si personne n'a parlé de hashtable.
Quelle que soit votre implémentation de set (même si « set » signifie ici un tableau simple), vous pouvez

1. mettre le contenu du premier ensemble dans hashtable et
2. itérer sur le second ensemble, en vérifiant si hashtable contient l'élément courant.

O(n)

Answer 2

intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

Si le test contains est à temps constant (comme dans un ensemble qui utilise une table de hachage comme implémentation), alors cet algorithme est O(n).

Answer 3

Pour tous les éléments de l'ensemble 1 : vérifiez si cet élément est dans l'ensemble 2. Vous pouvez implémenter un ensemble qui a amorti le temps de consultation O(1).