A complexidade do tempo da operação de interseção do conjunto em Python depende do método usado e do tamanho dos conjuntos envolvidos. Aqui está um colapso:
1. Usando o operador `&` ou o método `interseção ()`: *
Caso médio: O (min (Len (set1), len (set2)))
*
Pior caso: O (n*m) onde n é o comprimento de um conjunto e m é o comprimento do outro, mas isso é muito improvável.
Explicação: * O `set` do Python é implementado usando uma tabela de hash. O algoritmo itera essencialmente através do conjunto menor e verifica se cada elemento está presente no conjunto maior. O operador `in` em um conjunto (verificação da associação) leva O (1) em média devido à pesquisa da tabela de hash.
* Portanto, se `set1` for menor, ele itera através de` set1` e executar uma pesquisa de tabela de hash em `set2` para cada elemento, resultando em complexidade O (LEN (Set1)). A mesma lógica se aplica se `set2` for menor.
* O pior caso de O (n* m) ocorreria se as colisões de hash fossem galopantes, degradando as pesquisas de conjunto de O (1) a O (n). Isso é altamente incomum com os bons algoritmos de hash do Python.
2. Usando o método `intersection_update ()` (interseção no local): *
Caso médio: O (Len (Set)) onde o conjunto é o conjunto que será atualizado.
*
Pior caso: O mesmo que `interseção ()` - improvável o (n*m)
Explicação: `Intesection_update ()` modifica o conjunto no qual é chamado, removendo elementos que não estão presentes no (s) outro (s). A complexidade do tempo é semelhante ao `interseção ()` porque ainda precisa verificar a associação no (s) outro (s).
Exemplo: `` `Python
set1 ={1, 2, 3, 4, 5}
set2 ={3, 5, 6, 7, 8}
Interseção usando e operador:
intersection_set =set1 &set2
Print (Intersection_set) # Saída:{3, 5}
Interseção usando o método de interseção ():
intersection_set =set1.intersection (set2)
Print (Intersection_set) # Saída:{3, 5}
Interseção usando o método intersection_update () (modifica o set1):
set1.intersection_update (set2)
Print (set1) # saída:{3, 5}
`` `
Tabela de resumo: | Método | Complexidade média do tempo do caso | Na pior das hipóteses complexidade do tempo (improvável) |
| ---------------------------- | ---------------------------- | ------------------------------------------ |
| `&` Operador | O (min (len (set1), len (set2))) | O (n*m) |
| `Intersecção ()` | O (min (len (set1), len (set2))) | O (n*m) |
| `intersection_update ()` | O (Len (Set)) | O (n*m) |
Tecla de takeaway: A operação de interseção do conjunto em Python é geralmente muito eficiente, graças ao uso de tabelas de hash. Geralmente, você pode assumir que é O (min (Len (set1), Len (set2))) para fins práticos.
