Какая сложность вставки в словарь

Вставка элемента в словарь в Python имеет среднюю сложность O(1) (амортизированная константная сложность). Это связано с хэш-табличной реализацией словарей.

Однако в редких случаях при коллизиях хэшей или необходимости рехеширования (увеличения размера таблицы) сложность может временно возрастать до O(n), но в среднем остаётся O(1).

Пример:

my_dict = {}
my_dict['key'] = 'value'  # O(1) в среднем

Нюансы:

• При частых вставках может потребоваться ресайз хэш-таблицы, что временно увеличивает сложность.
• Для больших словарей важно учитывать хэш-функцию ключей: плохие хэши могут увеличить коллизии.