Каква е времевата сложност при добавяне и премахване на елемент в речник в Python?

В Python речникът е реализиран на базата на хеш таблица, което осигурява средно времева сложност O(1) за операциите добавяне и премахване на елементи.

• Добавяне на елемент: изчислява се хешът на ключа и елементът се вмъква в съответната клетка. Средно това отнема константно време.
• Премахване на елемент: също се извършва чрез хеша на ключа и средно отнема O(1).

Въпреки това, в най-лошия случай (например, при много колизии), операциите могат да деградират до O(n), където n е броят на елементите в речника, но такива случаи са изключително редки благодарение на добрата реализация и динамичното разширяване на речника.

Пример:

my_dict = {}
my_dict['key'] = 'value'  # добавяне — O(1)
del my_dict['key']          # премахване — O(1)