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

programa que haga las operaciones de conjuntos en java

Question

¿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 contra del tiempo de ejecución.

Answer 1

Bueno, vas a tener que mirar cada elemento de A , así que debe ser al menos tiempo lineal en el tamaño de A

Un algoritmo O(A+B) es fácil usando hashtables (almacena elementos de B en una tabla hash, luego busca 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.

Answer 2

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

1. Vea si A es un subconjunto de B según el filtro Bloom
2. En caso afirmativo, haz un control minucioso

Answer 3

Si tiene una lista de las letras y los pares de letras menos comunes en su conjunto de cuerdas, puede almacenar sus conjuntos ordenados con sus letras menos comunes y sus pares de letras y maximizar sus posibilidades de descartar las 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 digramas 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 de manera similar los datos al poner 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.