Python中字典新增键值对及update操作的时间复杂度是多少

单键直接插入的复杂度 #

使用d['key'] = 'value'的方式新增单个键值对时：

• 平均时间复杂度为 O(1)，这是字典底层基于哈希表实现的特性，正常场景下哈希冲突概率极低，插入可以在常数时间内完成
• 最坏时间复杂度为 O(n)，仅在所有键的哈希值完全冲突的极端场景下会触发，实际使用中几乎不会遇到

update 方法插入的复杂度 #

dict.update() 本质是遍历传入的所有键值对，逐个执行插入操作，因此时间复杂度和传入的键值对数量直接相关：

• 平均时间复杂度为 O(k)，其中 k 是传入 update 的参数包含的键值对总数
• 最坏时间复杂度为 O(kn)，仅在极端哈希冲突场景下出现

你给出的示例中，传给 update 的字典仅包含1个键值对，因此该场景下的平均时间复杂度和单键直接插入一致，为 O(1)。

内容的提问来源于stack exchange，提问作者Leonardus Chen