Le calcul de définir l'intersection, dans le temps linéaire?

Est-il un algorithme qui, étant donnés deux ensembles, calcule leur intersection dans le temps linéaire?

Je peux courir deux for boucles de vérifier toutes les paires d'éléments, les éléments de l'enregistrement que je trouve dans les deux ensembles. Cependant, la runninng temps O(n2). Comment dois-je faire en O(n) le temps?

  • POURQUOI serait-il jamais être n^2? N'est pas "évident" solution en O(n), et nous devrions être en train d'essayer de trouver une meilleure?
InformationsquelleAutor NEO | 2011-01-09
  1. 34

    Qui dépend de votre mise en œuvre.

    Si vous avez une table de hachage set (O(1) recherche), alors l'approche indiquée par tous les autres affiches est correct. Itérer sur tous les éléments dans le premier set. Si c'est dans le deuxième set, puis l'ajouter à la suite. Cela s'exécute en O(n) fois.

    Si vous avez un arbre de jeu (O(lg n) de recherche), alors cette approche fonctionne, mais il s'exécute en temps O(n lg n) fois. Vous pouvez faire mieux; il y a un O(n) solution. Je suppose que vous avez une sorte de itérateur qui peut traverser les éléments des deux ensembles dans l'ordre croissant. Si vous le faites, alors la question est "donné deux listes dans l'ordre de tri, de trouver leur point d'intersection." Cela peut être fait en utilisant une version modifiée de l'algorithme que vous utilisez pour fusionner les deux chaînes de montagnes. L'idée est de garder la trace des deux itérateurs. À chaque étape, de comparer les premiers éléments de l'plages. Si elles sont égales, ajouter l'élément à l'intersection et de faire progresser à la fois les itérateurs de l'avant. Si le premier est inférieur au second, puis avancer la première itérateur. Si le premier élément est plus grand, puis l'avance, la deuxième itérateur. Cela s'exécute en temps O(n) car chaque itération consomme au moins un élément, et il y a seulement O(n) éléments au total.

    • Les deux ensembles ne sont pas triés.Que faire Si j'utilise de fusion de tri de la technique et de suivre votre méthode de comparaison les premiers éléments de l'plages,mais im pas sûr que cela fonctionne en O(n) bcoz de fusion de tri prend O(nlogn)temps
    • Si vous mettez les séries dans l'ordre de tri en O(n lg n) le temps, cette technique devrait fonctionner, mais il ne s'exécute pas dans le temps linéaire, car de la sorte les frais généraux. Comment se définit-il représenté?
    • les ensembles sont dans un tableau.
    • Je veux dire 2 diff entier tableaux
    • Juste une itération sur les deux listes, en les ajoutant à une table de hachage, puis appliquer le "intersection de deux tables de hachage" de l'algorithme.
    • Je pense que je l'ai eu nw.Merci

    InformationsquelleAutor templatetypedef
  2. 9

    Je me demande personne n'a mentionné de table de hachage.

    Quel que soit votre jeu de mise en œuvre (même si 'set' signifie ici un tableau simple), vous pouvez

    1. mettre le contenu de la première série dans la table de hachage et
    2. itération sur le deuxième set, vérifier si la table de hachage contient l'élément courant.

    O(n)

    InformationsquelleAutor Nikita Rybak
  3. 2
    intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

    Si le contains test est la constante de temps (comme dans un jeu qui utilise une table de hachage comme une mise en œuvre), alors cet algorithme est O(n).

    • Si a et b sont de la même définit ensuite l'algorithme prend O(n^3) fois depuis la recherche en "b" et l'ajout d'un élément de "résultat" prend O(n) fois. L'ajout d'un élément à un tableau basé prend O(n) fois depuis jeux ne peuvent pas avoir dupliqué élément. La duplication vérification est effectuée sur chaque ajout. Si le résultat et b est basé sur la table de hachage puis même si vous ne pouvez pas être sûr que la recherche et l'addition prend O(1) fois, il peut prendre en O(n) ainsi.
    InformationsquelleAutor sjr
  4. 2

    Combiner les deux tableaux, et de compter les pas d'occurrences de chaque élément dans ce combiné de tableau et de mettre ces derniers dans un nouveau tableau. Ensuite, vérifiez ce nombre de tableau pour les entrées qui contiennent 2, ces éléments sont dans l'intersection des deux ensembles.

    InformationsquelleAutor
  5. 0

    Pour tous les éléments de l'ensemble 1: Vérifier si l'élément est dans l'ensemble 2. Vous pouvez mettre en œuvre un Ensemble qui a amorti O(1) recherche du temps.

    • Autre option si vous utilisez une triés-basée sur l'arbre de jeu au lieu d'une table de hachage basée sur: Itérer sur les deux ensembles dans l'ordre de tri, le passage à l'élément suivant de la actuellement sur le "plus" ensemble. O(n) dans le nombre total d'éléments.
    InformationsquelleAutor Anon.
  6. 0

    si l'une des deux listes est ordonné, alors nous pouvons commencer avec la liste non ordonnée

    FUNCTION: INTERSECTION ( LIST A, LIST B )
{
   CREATE C AS EMPTY LIST

   FOR EVERY: NUMBER n IN A
   {
        IF BINARY-SEARCH(n) IN B
        {
            ADD n TO C
        }
   }

   RETURN C
}

    Time Complexity = O(n O(BINARY-SEARCH)) = O(n log n)

    si la liste B est hashed, puis nous avons BIG-THETA(C n + T(hash))

    où les GRANDS-THETA est l'asymptotique de la moyenne, et C est un constant
    et T(hash) est le temps nécessaire pour la fonction de hachage

    InformationsquelleAutor Khaled Khunaifer