Algoritmo para verificar si el conjunto A es un subconjunto del conjunto B más rápido que el tiempo lineal - algoritmo, conjunto, subconjunto

¿Hay un algoritmo (preferiblemente tiempo constante) para verificar si el conjunto A es un subconjunto del conjunto B?

Crear las estructuras de datos para facilitar este problema no cuenta en el tiempo de ejecución.

Respuestas

Bueno, vas a tener que mirar cada elemento de A, por lo que debe ser al menos un tiempo lineal en el tamaño de A.

Un O(A+B) El algoritmo es fácil usando tablas hash (almacenar elementos de B en una tabla hash, luego busca cada elemento de A). No creo que puedas hacerlo mejor a menos que conozcas alguna estructura avanzada para B. Por ejemplo, si B Se almacena en el orden ordenado, usted puede hacer O(A log B) utilizando la búsqueda binaria.

Puede ir para el filtro de floración (http: // en.wikipedia.org/wiki/Bloom_filter). Sin embargo, puede haber falsos positivos, que pueden solucionarse mediante el método mencionado por Keith anteriormente (pero tenga en cuenta que la peor complejidad del hashing NO es O (n), pero puede hacer O (nlogn).

1. Ver si A es un subconjunto de B según el filtro Bloom
2. Si es así, entonces haga una comprobación minuciosa

Si tienes una lista de las letras menos comunes.y pares de letras en su conjunto de cuerdas, puede almacenar sus conjuntos ordenados con sus letras y pares de letras menos comunes y maximizar sus posibilidades de descartar coincidencias negativas lo más rápido posible. No me queda claro qué tan bien se combinaría esto con un filtro de floración. Probablemente una tabla hash funcionará ya que no hay muchos digrams y letras.

Si tuviera alguna información sobre el tamaño máximo de los subconjuntos o incluso un tamaño común, podría preprocesar los datos de manera similar si coloca todos los subconjuntos de un tamaño determinado en un filtro de floración como se mencionó.

También podrías hacer una combinación de ambos.