He aquí por qué:
* Implementación: Los conjuntos de Python se implementan utilizando tablas hash. Esto permite búsquedas muy rápidas (en promedio, o (1)).
* Proceso de intersección: La operación de intersección esencialmente itera a través del conjunto y verifica más pequeños si cada elemento existe en el conjunto más grande.
* Costo de búsqueda: La verificación de la existencia de un elemento en el conjunto más grande es, en promedio, una operación O (1) debido a la implementación de la tabla hash.
Por lo tanto, si `S1` es el conjunto más pequeño, la operación itera a través de` S1` (len (S1) veces) y realiza una búsqueda O (1) en `S2` para cada elemento. Esto da como resultado una complejidad total de tiempo de O (len (S1) * 1) =O (len (S1)). Del mismo modo, si `S2` es más pequeño, la complejidad es O (len (S2)). Por lo tanto, la complejidad general es O (Min (LEN (S1), LEN (S2))).
El peor de los casos:
Si bien el caso promedio es O (min (len (S1), len (S2))), el peor de los casos es O (len (S1) * len (S2)) si hay muchas colisiones hash, lo que lleva a las búsquedas O (n) en lugar de o (1). Sin embargo, esto es raro en la práctica con el hashing bien diseñado de Python.
Ejemplo:
`` `Python
set1 ={1, 2, 3, 4, 5}
set2 ={3, 5, 6, 7, 8, 9, 10}
intersection_set =set1 y set2 # o set1.intersection (set2)
print (intersection_set) # output:{3, 5}
`` `` ``
En este ejemplo, la complejidad del tiempo de la operación de intersección estaría más cerca de O (len (SET1)) porque `SET1` es más pequeño.