Tidskomplexiteten för uppsättningskorsningsoperationen i Python beror på den använda metoden och storleken på de inblandade uppsättningarna. Här är en uppdelning:
1. Använda metoden `&'eller` korsningen () `metod:
* Genomsnittligt fall: O (min (len (set1), len (set2)))
* värsta fall: O (n*m) där n är längden på en uppsättning och m är längden på den andra, men detta är mycket osannolikt.
Förklaring:
* Pythons `set 'implementeras med en hashtabell. Algoritmen itereras i huvudsak genom den mindre uppsättningen och kontrollerar om varje element finns i den större uppsättningen. `I '-operatören på en uppsättning (kontroll för medlemskap) tar i genomsnitt O (1) i genomsnitt på grund av hashtabellen.
* Därför, om "set1" är mindre, itereras det genom "set1" och utför en hash -tabelluppslag i "set2" för varje element, vilket resulterar i o (len (set1)) komplexitet. Samma logik gäller om `set2 'är mindre.
* Det värsta fallet med o (n* m) skulle inträffa om hashkollisioner är utbredda, vilket förnedrar uppsättningen från O (1) till O (n). Detta är mycket ovanligt med Pythons goda hash -algoritmer.
2. Använda metoden `Intersection_Update ()` (på plats korsning):
* Genomsnittligt fall: O (len (set)) där set är den uppsättning som kommer att uppdateras.
* värsta fall: Samma som `korsning ()` - osannolikt o (n*m)
Förklaring:
`Intersection_Update ()` modifierar den uppsättning som den kallas och tar bort element som inte finns i de andra uppsättningarna. Tidskomplexiteten liknar "skärningspunkten ()" eftersom den fortfarande måste kontrollera medlemskap i de andra uppsättningarna.
Exempel:
`` `python
set1 ={1, 2, 3, 4, 5}
set2 ={3, 5, 6, 7, 8}
korsning med &operatör:
Intersection_set =set1 &set2
tryck (Intersection_set) # output:{3, 5}
korsning med hjälp av korsning () Metod:
Intersection_set =set1.intersection (set2)
tryck (Intersection_set) # output:{3, 5}
korsning med hjälp av Metod Intersection_Update () (modifierar set1):
set1.intersection_update (set2)
utskrift (set1) # output:{3, 5}
`` `
Sammanfattningstabell:
| Metod | Genomsnittlig falltidskomplexitet | Värsta fall Tidskomplexitet (osannolikt) |
| -------------------------- | ------------------------------ | --------------------------------------------- |
| `&` Operatör | O (min (len (set1), len (set2))) | O (n*m) |
| `korsning ()` | O (min (len (set1), len (set2))) | O (n*m) |
| `Intersection_Update ()` | O (len (set)) | O (n*m) |
Nyckel takeaway: Uppsättningskorsningsoperationen i Python är i allmänhet mycket effektiv tack vare användningen av hashtabeller. Du kan vanligtvis anta att det är o (min (len (set1), len (set2))) för praktiska ändamål.
