Aká je časová zložitosť priesečníka SET v Pythone?

Časová zložitosť operácie priesečníka SET v Pythone závisí od použitej metódy a veľkosti príslušných súborov. Tu je porucha:

1. Pomocou operátora `&` alebo metóda `intersection ()`:

* Priemerný prípad: O (min (Len (set1), len (set2))))))))))

* Najhorší prípad: O (n*m), kde n je dĺžka jednej sady a m je dĺžka druhej, ale je to veľmi nepravdepodobné.

Vysvetlenie:

* Python's `Set` je implementovaný pomocou hashovej tabuľky. Algoritmus v podstate iteruje cez menšiu sadu a kontroluje, či je každý prvok prítomný vo väčšej sade. Operátor „in“ na sade (kontrola členstva) má v priemere O (1) v dôsledku vyhľadávania tabuľky hash.

* Preto, ak je `set1` menší, iteruje sa prostredníctvom` set1` a vykonáva vyhľadávanie tabuľky hash v `set2` pre každý prvok, čo vedie k zložitosti o (len (set1))). Rovnaká logika platí, ak je `set2` menší.

* Najhorší prípad O (n* m) by sa vyskytol, ak by hashové zrážky nekontrolovali a degradovali stanovené vyhľadávania z O (1) do O (n). To je veľmi nezvyčajné s Pythonovým dobrým algoritmom hashovania.

2. Pomocou metódy `intersection_update ()` (križovatka na mieste):

* Priemerný prípad: O (Len (set)), kde set je sada, ktorá bude aktualizovaná.

* Najhorší prípad: Rovnaké ako `priesečník ()` - nepravdepodobné O (n*m)

Vysvetlenie:

`intersection_update ()` Modifikuje súpravu, na ktorej sa volá, a odstraňuje prvky, ktoré nie sú prítomné v druhej sade. Časová zložitosť je podobná ako „priesečník ()“, pretože stále potrebuje skontrolovať členstvo v ostatných súboroch.

Príklad:

`` `Python

set1 ={1, 2, 3, 4, 5}

set2 ={3, 5, 6, 7, 8}

priesečník pomocou a operátora:

intersection_set =set1 &set2

tlač (intersection_set) # výstup:{3, 5}

priesečník pomocou metódy intersekcie ():

intersection_set =set1.intersection (set2)

tlač (intersection_set) # výstup:{3, 5}

priesečník s použitím metódy intersection_update () (modifikuje set1):

set1.intersection_update (set2)

tlač (set1) # výstup:{3, 5}

`` `

Súhrnná tabuľka:

| Metóda | Priemerná zložitosť času v prípade Zložitosť najhoršieho prípadu (nepravdepodobné)

| ---------------------------- | --------------------------------- | ------------------------------------- |

| `&` Prevádzkovateľ | O (min (Len (set1), len (set2))) | O (n*m) |

| `priesečník ()` | O (min (Len (set1), len (set2))) | O (n*m) |

| `intersection_update ()` | O (len (set)) | O (n*m) |

Kľúčové kroky: Prevádzka priesečníka v Pythone je vo všeobecnosti veľmi efektívna vďaka použitiu hashových tabuliek. Zvyčajne môžete predpokladať, že na praktické účely je O (min (len Set1), Len (set2)))).

• Predchádzajúca strana: Aká je časová zložitosť križovatky v pythonových súpravách? 
• Ďalšia strana: Ako znásobiť plaváky v Pythone?