¿Existe algún algoritmo (preferiblemente tiempo constante) para verificar si el conjunto A es un subconjunto del conjunto B?Algoritmo para verificar si el conjunto A es un subconjunto del conjunto B más rápido que el tiempo lineal
Crear las estructuras de datos para facilitar este problema no cuenta en contra del tiempo de ejecución.
Bueno, vas a tener que mirar cada elemento de A, por lo que debe ser al menos tiempo lineal en el tamaño de A.
Un algoritmo O(A+B) es muy fácil usando tablas hash (almacenar elementos de B en una tabla hash, a continuación, buscar cada elemento de A). No creo que pueda hacerlo mejor a menos que sepa alguna estructura de avance para B. Por ejemplo, si B se almacena en orden ordenado, puede hacer O(A log B) usando la búsqueda binaria.
Si ordena ambos conjuntos, puede comparar el encabezado de las dos colecciones. El rendimiento de este algoritmo es O (A + B) – Miguel
Puede optar por el filtro bloom (http://en.wikipedia.org/wiki/Bloom_filter). Sin embargo puede haber falsos positivos, que pueden ser abordados por el método mencionado por Keith anterior (pero tenga en cuenta que el peor de los casos complejidad de hash no es O (n), pero se puede hacer O (nlogn).
Me gusta este algoritmo porque hacer un postprocesamiento es muy rápido en mi caso. El filtro de floración se ejecutará en el servidor y el procesamiento posterior del conjunto de resultados se ejecutará en el lado del cliente. – volni
Si usted tiene una lista de las letras menos comunes y los pares de letras en su juego de cuerdas, que pueden almacene sus juegos ordenados con sus letras menos comunes y sus pares de letras y maximice sus posibilidades de descartar las coincidencias negativas lo más rápido posible. No está claro para qué se combinaría esto con un filtro de floración. Probablemente una tabla hash funcionará, ya que no hay muchos digramas y letras.
Si tiene alguna información sobre el tamaño máximo de subconjuntos o incluso un tamaño común, puede preprocesar los datos de forma similar si coloca todos los subconjuntos de un tamaño determinado en un filtro de floración como se mencionó.
También podría hacer una combinación de ambos.
Encontré esta respuesta: http://stackoverflow.com/a/1338515/174674 – volni
Necesitamos más información sobre el contenido del conjunto. Los algoritmos generales no le darán una complejidad de tiempo constante. Al menos, ninguno que yo sepa. –
Los elementos establecidos son cadenas pero, por supuesto, podemos ejecutarlos a través de un hash o asignarles posiciones en un conjunto de bits si eso daría lugar a un algoritmo más rápido. – volni