En Python puedes obtener la intersección de dos conjuntos haciendo:
>>> s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9} >>> s2 = {0, 3, 5, 6, 10} >>> s1 & s2 set([3, 5, 6]) >>> s1.intersection(s2) set([3, 5, 6]) ¿Alguien sabe la complejidad de este algoritmo de intersección ( & )?
EDITAR: Además, ¿alguien sabe cuál es la estructura de datos detrás de un conjunto de Python?
La respuesta parece ser una consulta del motor de búsqueda de distancia . También puede utilizar este enlace directo a la página de Complejidad de tiempo en python.org . Sumario rápido:
Average: O(min(len(s), len(t)) Worst case: O(len(s) * len(t))
EDITAR: Como señala Raymond a continuación, es probable que no se produzca el “peor de los casos”. Lo incluí originalmente para ser exhaustivo, y lo dejo para proporcionar un contexto para la discusión a continuación, pero creo que Raymond tiene razón.
El algoritmo de intersección siempre se ejecuta en O (min (len (s1), len (s2))).
En Python puro, se ve así:
def intersection(self, other): if len(self) <= len(other): little, big = self, other else: little, big = other, self result = set() for elem in little: if elem in big: result.add(elem) return result
[Respuesta a la pregunta en la edición adicional] La estructura de datos detrás de los conjuntos es una tabla hash .
Establecer la intersección de dos conjuntos de tamaños m,n se puede lograr con O(max{m,n} * log(min{m,n})) de la siguiente manera: Supongamos que m << n
1. Represent the two sets as list/array(something sortable) 2. Sort the **smaller** list/array (cost: m*logm) 3. Do until all elements in the bigger list has been checked: 3.1 Sort the next **m** items on the bigger list(cost: m*logm) 3.2 With a single pass compare the smaller list and the m items you just sorted and take the ones that appear in both of them(cost: m) 4. Return the new set
El bucle en el paso 3 se ejecutará para n/m iteraciones y cada iteración tomará O(m*logm) , por lo que tendrá una complejidad de tiempo de O(nlogm) para m << n.
Creo que ese es el mejor límite inferior que existe