Tidskomplexiteten för korsningens operation i Python -uppsättningar med användning av metoden `&'eller` korsning () `är
o (min (len (S1), len (S2)) I genomsnitt, där "S1" och "S2" är uppsättningarna korsade.
Här är varför:
* Implementering: Pythonuppsättningar implementeras med hashtabeller. Detta möjliggör mycket snabba uppslag (i genomsnitt O (1)).
* korsningsprocess: Korsningsoperationen itereras i huvudsak genom den mindre uppsättningen och kontrollerar om varje element finns i den större uppsättningen.
* Sökningskostnad: Att kontrollera för att det finns ett element i den större uppsättningen är i genomsnitt en O (1) operation på grund av hashtabellimplementeringen.
Därför, om "S1" är den mindre uppsättningen, itererar driften genom "S1" (Len (S1) gånger) och utför en O (1) uppslagning i "S2" för varje element. Detta resulterar i en total tidskomplexitet av O (len (S1) * 1) =O (len (S1)). På samma sätt, om "S2" är mindre, är komplexiteten O (len (S2)). Således är den övergripande komplexiteten O (min (len (S1), len (S2))).
Worst-Case-scenario:
Medan det genomsnittliga fallet är O (min (len (S1), len (S2))), är det värsta fallet o (len (s1) * len (S2)) om det finns många hashkollisioner, vilket leder till o (n) uppslag istället för o (1). Detta är emellertid sällsynt i praktiken med Pythons väl utformade hashing.
Exempel:
`` `python
set1 ={1, 2, 3, 4, 5}
set2 ={3, 5, 6, 7, 8, 9, 10}
Intersection_set =set1 &set2 # eller set1.intersection (set2)
tryck (Intersection_set) # output:{3, 5}
`` `
I det här exemplet skulle korsningens operationens tidskomplexitet vara närmare O (len (set1)) eftersom `set1 'är mindre.
