A complexidade do tempo da operação de interseção nos conjuntos de python, usando o operador `&` ou o método` interseção () `, é
o (min (len (s1), len (s2))) Em média, onde `s1` e` s2` são os conjuntos que estão sendo cruzados.
Aqui está o porquê:
*
Implementação: Os conjuntos de Python são implementados usando tabelas de hash. Isso permite pesquisas muito rápidas (em média, O (1)).
*
Processo de interseção: A operação de interseção itera essencialmente através do conjunto menor e verifica se existe cada elemento no conjunto maior.
*
Custo da pesquisa: A verificação da existência de um elemento no conjunto maior é, em média, uma operação O (1) devido à implementação da tabela de hash.
Portanto, se `s1` for o conjunto menor, a operação itera através de` s1` (len (s1) vezes) e executa uma pesquisa o (1) em `s2` para cada elemento. Isso resulta em uma complexidade total de tempo de O (Len (S1) * 1) =O (Len (S1)). Da mesma forma, se `s2` for menor, a complexidade é O (Len (S2)). Assim, a complexidade geral é O (min (LEN (S1), LEN (S2))).
Cenário de pior caso: Enquanto o caso médio é O (min (LEN (S1), LEN (S2))), o pior cenário é O (Len (S1) * Len (S2)) se houver muitas colisões de hash, levando a pesquisas O (n) em vez de O (1). No entanto, isso é raro na prática com o hash bem projetado de Python.
Exemplo: `` `Python
set1 ={1, 2, 3, 4, 5}
set2 ={3, 5, 6, 7, 8, 9, 10}
intersection_set =set1 &set2 # ou set1.intersection (set2)
Print (Intersection_set) # Saída:{3, 5}
`` `
Neste exemplo, a complexidade do tempo da operação de interseção estaria mais próxima de O (Len (set1)) porque `set1` é menor.
