在 Python 中向字典添加新的键值对的时间复杂度是多少？

Question

添加一个 new 键值对的时间复杂度是多少：

d = dict()
d.update({'key':'value'})

这里找不到https://wiki.python.org/moin/TimeComplexity

Answer 1

python 字典是 hash table

下面是“大 O 表示法中的时间复杂度”的 table（取自上面相同的 link）

算法平均最坏情况

Space O(n)1 O(n)

搜索 O(1) O(n)

插入 O(1) O(n)

删除 O(1) O(n)

Answer 2

Python 中词典的更新功能可以通过几种不同的方式调用。第一个是作为键到值的映射，后跟可选的关键字参数。第二种方式是元组列表，后跟可选的关键字参数。第三个是作为一系列关键字参数。我们可以在 builtins.pyi:

中看到这些函数存根

@overload
def update(self, __m: Mapping[_KT, _VT], **kwargs: _VT) -> None: ...
@overload
def update(self, __m: Iterable[Tuple[_KT, _VT]], **kwargs: _VT) -> None: ...
@overload
def update(self, **kwargs: _VT) -> None: ...

还有这个更实际的例子：

d_obj = dict()
d_obj.update({'a':1},b=2)
d_obj.update([('c',3)],d=4)
d_obj.update(e=5)
print(d_obj)

对于这些实现中的每一个，Python 将遍历传入的每个参数并在常数时间内检查键是否在字典中。如果键在字典中，该函数会将键设置为其新值。如果不是，则该函数会将键添加到字典并设置其值。由于所有这些添加和设置操作都可以假设在恒定时间内完成，我们可以假设传递给 update() 的每个单独项目都在恒定时间内完成，因此我们得到 O(1 * n) 其中 n 等于传递给 update() 的单个键值对的数量。因此更新函数的时间复杂度为O(n).

Answer 3

由于“设置项目”被列为 O(1) 平均情况和 O(n) 最坏情况，我相信你可以假设这也是 update() 的复杂性。