Aká je časová zložitosť pridania a odstránenia prvku v slovníku v Pythone?

V Pythone je slovník implementovaný na základe hashovacej tabuľky, čo zabezpečuje v priemere časovú zložitosť O(1) pre operácie pridávania a odstraňovania prvkov.

• Pridanie prvku: vypočíta sa hash kľúča a prvok sa vloží do príslušnej bunky. V priemere to trvá konštantný čas.
• Odstránenie prvku: tiež sa vykonáva pomocou hashu kľúča a v priemere trvá O(1).

Avšak v najhoršom prípade (napríklad pri veľkom počte kolízií) sa operácie môžu zhoršiť na O(n), kde n je počet prvkov v slovníku, ale také prípady sú mimoriadne zriedkavé vďaka dobrej implementácii a dynamickému rozširovaniu slovníka.

Príklad:

my_dict = {}
my_dict['key'] = 'value'  # pridanie — O(1)
del my_dict['key']          # odstránenie — O(1)