algorithm - why - instagram hashtags on comments or caption

La computación establece intersección en tiempo lineal?

Question

¿Hay un algoritmo que, dados dos conjuntos, compute su intersección en tiempo lineal?

Puedo ejecutar dos bucles para verificar todos los pares de elementos, registrando los elementos que encuentro en ambos conjuntos. Sin embargo, el tiempo de ejecución será O (n ² ). ¿Cómo hago esto en O (n) vez?

Answer 1

Combine las dos matrices y cuente el número de ocurrencias de cada elemento en esta matriz combinada y colóquelas en una nueva matriz. Luego revise esta matriz de conteo para las entradas que contienen 2, esos elementos están en la intersección de los dos conjuntos.

Answer 2

Eso depende de la implementación de tu conjunto.

Si tiene un conjunto de hash (búsqueda O (1)), entonces el enfoque indicado por todos los otros carteles es correcto. Iterate a través de todos los elementos en el primer conjunto. Si está en el segundo conjunto, agréguelo al resultado. Esto se ejecuta en O (n) tiempo.

Si tiene un conjunto de árbol (búsqueda O (lg n)), este enfoque funcionará, pero se ejecuta en O (n lg n) tiempo. Puedes hacerlo mejor; hay una solución de O (n). Supongo que tienes algún tipo de iterador que puede atravesar los elementos de los dos conjuntos en orden ascendente. Si lo hace, entonces la pregunta es "dos listas dadas en orden, encuentre su intersección". Esto se puede hacer usando una versión modificada del algoritmo que usa para fusionar dos rangos. La idea es hacer un seguimiento de los dos iteradores. En cada paso, compare los primeros elementos de los rangos. Si son iguales, agregue el elemento a la intersección y avance ambos iteradores hacia adelante. Si el primero es menor que el segundo, avance el primer iterador. Si el primer elemento es mayor, avance el segundo iterador. Esto se ejecuta en el tiempo O (n) porque cada iteración consume al menos un elemento, y solo hay O (n) elementos en total.

Answer 3

Me pregunto que nadie mencionó hashtable.
Independientemente de la implementación de su conjunto (incluso si ''set'' aquí significa una matriz simple), puede

1. poner los contenidos del primer conjunto en hashtable y
2. iterar sobre el segundo conjunto, verificando si hashtable contiene el elemento actual.

O(n)

Answer 4

Para todos los elementos en el conjunto 1: compruebe si ese elemento está en el conjunto 2. Puede implementar un conjunto que tiene amortizado O (1) tiempo de búsqueda.

Answer 5

si se ordena una de las dos listas, entonces podemos comenzar con la lista desordenada

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 lista B es hashed , entonces tenemos BIG-THETA(C n + T(hash))

donde BIG-THETA es el promedio asintótico, y C es una constant y T(hash) es el tiempo necesario para la función hash

Answer 6

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

  return result

Si la prueba contains tiempo constante (como en un conjunto que utiliza una tabla hash como una implementación), este algoritmo es O(n) .