Aká je časová zložitosť križovatky v pythonových súpravách?

Časová zložitosť priesečníka v pythonových množinách pomocou operátora `&` alebo metóda „intersection ()`, je o (min (len (s1), Len (s2)))) )) V priemere, kde „s1` a` s2` sú pretínané súbory.

Tu je dôvod:

* implementácia: Sady Python sa implementujú pomocou hashových tabuliek. To umožňuje veľmi rýchle vyhľadávanie (v priemere o (1)).

* Proces priesečníka: Prevádzka križovatky v podstate iteruje prostredníctvom menšej sady a kontroluje, či každý prvok existuje vo väčšej sade.

* Náklady na vyhľadávanie: Kontrola existencie prvku vo väčšej sade je v priemere operácia O (1) v dôsledku implementácie tabuľky hash.

Preto, ak je `S1` menšia súprava, operácia iteruje cez` S1` (Len (S1) krát) a vykonáva vyhľadávanie O (1) v `S2` pre každý prvok. To má za následok celkovú časovú zložitosť O (Len (S1) * 1) =o (len (s1)). Podobne, ak je `S2` menší, zložitosť je O (Len (S2)). Celková zložitosť je teda O (min (Len (S1), Len (S2)))).

Najhorší scenár:

Zatiaľ čo priemerný prípad je O (min (Len (S1), Len (S2))), najhorší scenár je O (Len (S1) * Len (S2)), ak existuje veľa hashových kolízií, čo vedie k vyhľadávaniu O (N) namiesto O (1). V praxi je to však zriedkavé s dobre navrhnutým hashovaním Pythona.

Príklad:

`` `Python

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

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

intersection_set =set1 &set2 # alebo set1.intersection (set2)

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

`` `

V tomto príklade by bola časová zložitosť časovej operácie križovatky bližšie k O (Len (set1)), pretože `set1` je menší.

• Predchádzajúca strana: Aká je časová zložitosť nájdenia maximálneho prvku v zozname pomocou funkcie Python Max? 
• Ďalšia strana: Aká je časová zložitosť priesečníka SET v Pythone?