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

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

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

以以下两个词典为例：

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

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

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

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

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

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

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

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