Considere conjuntos de valores (representados como matrices ordenadas sin duplicados y con un tamaño conocido (es decir, el tamaño puede obtenerse en O (1)). Los valores pueden probarse para la igualdad en el tiempo O (1). Quiero para obtener el conjunto de valores que están presentes en al menos k conjuntos diferentes entre los n .
El algoritmo obvio para hacer esto es revisar todos los conjuntos, contar el número de ocurrencias de cada valor y devolver aquellos con un recuento superior a . Sin embargo, en algunos casos, puede hacerlo mejor: por ejemplo, cuando n = k = 2 y cuando un conjunto S 1 es mucho más pequeño que el otro conjunto S 2 , es más eficiente observar todos los elementos de S 1 y realizar una búsqueda binaria para cada uno de ellos en S 2 : el enfoque de búsqueda binaria cuesta O ( | S 1 | log ( | S 2 | mientras que el enfoque ingenuo cuesta O ( | S 1 | + | S 2 | ) que es peor cuando | S 1 | < < | S 2 | .
Con esto en mente, ¿en qué situaciones podemos hacerlo mejor que el algoritmo ingenuo? (Si este es un problema bien conocido, me encantaría saber su nombre habitual y tener referencias).
fuente
Respuestas:
fuente
Su problema es similar al problema de minería de datos de encontrar conjuntos de elementos frecuentes , también conocido como aprendizaje de reglas de asociación . Si entendí correctamente, su problema puede reducirse a encontrar conjuntos de ítems frecuentes de cardinalidad 1 (es decir, singletons) con soporte > = k . Por supuesto, los algoritmos disponibles (como Apriori, Eclat, D-CLUB, etc.) para el problema también permiten determinar conjuntos de ítems frecuentes de cardinalidad> 1.
fuente