Mi a hozzáadás és törlés időbeli komplexitása egy szótárban Pythonban?

Pythonban a szótár egy hash-tábla alapjaira épül, ami átlagosan O(1) időkomplexitást biztosít az elemek hozzáadására és eltávolítására.

• Elem hozzáadása: a kulcs hash értékét számítják ki, és az elem a megfelelő cellába kerül. Átlagosan ez konstans időt vesz igénybe.
• Elem eltávolítása: szintén a kulcs hash értéke alapján történik, és átlagosan O(1) időt vesz igénybe.

Azonban a legrosszabb esetben (pl. sok ütközés esetén) a műveletek O(n)-re romolhatnak, ahol n a szótárban lévő elemek száma, de ilyen esetek rendkívül ritkák a jó implementáció és a dinamikus bővítés miatt.

Példa:

my_dict = {}
my_dict['key'] = 'value'  # hozzáadás — O(1)
del my_dict['key']          # törlés — O(1)