python - 在python中比较两个字典的时间复杂度是多少

Question

有人可以解释一下操作d1 == d2的时间复杂度吗，其中d1和d2是2个Python字典

Answer 1

简短回答:如果两个字典具有相同数量的项目，则需要 O(n) 次相等性检查，其中 n 个数量的项目。如果两个字典的项目数量不同，则需要 O(1)，因为这两个字典是不同的。请注意，相等性检查的计算成本可能很高。

<小时/>

这里估计时间复杂度的一个问题是字典可以包含列表、其他字典、树等值。

以下两本词典为例:

{ 1: [1,4,2,5] } == { 1 : [1,4,2,6] }

这里两个字典都有相同的键，但是为了检查列表是否相同，最坏的情况是，花费的时间与列表的大小呈线性关系。

但是，我们可以根据需要进行的比较数量来进行讨论。如果我们假设字典具有恒定的查找时间，则这将是 O(n)，其中 n 是两个字典的元素数量。

我们可以查看 CPython source code [GitHub]在 dict_equal(PyDictObject *a, PyDictObject *b) 函数中。

该函数将首先检查两个字典是否包含相同数量的对象。如果不是这样，那么两个字典当然不可能相等。

接下来我们可以迭代两个字典之一。对于第一个字典中的每个键/值对，我们查找第二个字典中是否存在该键。如果不存在这样的值，那么我们就知道两个字典不相等，因此我们可以返回False。

如果这样的键存在，我们在第一个字典和第二个字典的对应值之间执行相等性检查。如果比较失败，我们可以返回False，因为这意味着两个字典有一个键对应的值不同。

如果对于字典的所有键，该键存在于另一个字典中，并且值被认为是相同的，我们可以返回True，因为这意味着所有键都存在于另一个字典中字典，对应的值也是一样的。