在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是两个字典的元素数。在

我们可以在dict_equal(PyDictObject *a, PyDictObject *b)函数中检查^{} source code [GitHub]。在

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

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

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

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