En Python se puede obtener la intersección de dos conjuntos hacer:Intersección complejidad
>>> 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 esta intersección (&) algoritmo?
EDITAR: Además, ¿alguien sabe cuál es la estructura de datos detrás de un conjunto de Python?
La respuesta parece ser a search engine query away. También puede usar este direct link to the Time Complexity page at python.org. Resumen rápido:
Average: O(min(len(s), len(t))
Worst case: O(len(s) * len(t))
EDIT: Como Raymond señala más adelante, el escenario de "peor de los casos" no es probable que ocurra. Originalmente lo incluí para que fuera minucioso, y lo dejo para proporcionar el contexto para la discusión a continuación, pero creo que Raymond tiene razón.
El intersection algorithm siempre se ejecuta en O (min (len (s1), len (s2)).
En Python puro, es 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 conjuntos es una hash table.
no ** siempre **, consulte: http://wiki.python.org/moin/TimeComplexity#set – juliomalegria
De acuerdo con el wiki que he vinculado anteriormente, el peor caso para 'elem in big' en su código es O (n) (aunque el promedio es, por supuesto, O (1)). Esa es la base para el peor caso de intersección de O (len (s) * len (t)). ¿Alguna idea de por qué? –
El "peor de los casos" asume datos que no son apropiados para su uso en la tabla hash utilizada por * dict * y * set *.Los datos tendrían que ser algo así que cada dato tuviera exactamente el mismo valor hash; esto obligaría a la tabla hash a hacer algo similar a una búsqueda lineal para hacer la comprobación \ _ \ _ contiene \ _ \ _. IOW, no me preocuparía por esto en absoluto. Establecer la intersección es ciegamente rápido: incluso reutiliza los valores hash almacenados internamente para que no tenga que realizar ninguna llamada a * hash() *. –
Set 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 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 se llevará a O(m*logm), por lo tendrá una complejidad de tiempo de O(nlogm) para m < < n.
Creo que es el mejor límite inferior que existe
ese es el peor caso desagradable, ¿no? – juliomalegria
¡Me sorprendió también! ¿Tal vez se trate de tener diferentes tipos de datos mezclados en los dos conjuntos que se cruzan? –
Parece que primero no se usa un género (que * requiere que los objetos tengan un pedido *), sino que simplemente hace una "sonda hash": tal vez para un mejor 'C' y promedio (y * sin requisito de pedido *) La complejidad máxima requerida, AFAIK, es sobre 'O (n log n) + O (n)', con un ordenamiento. Sin embargo, Big-O es un límite superior y hay consideraciones prácticas, así que ... –