Python中比较两个字典的时间复杂度是多少？

Question

4

请问一下，当d1和d2是两个Python字典时，操作d1 == d2的时间复杂度是什么？

- Jitesh Malipeddi

1

一个字典可以包含任意复杂的结构。最坏情况无法确定。 - Klaus D.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Willem Van Onsem · Accepted Answer

简短回答：如果两个字典具有相同数量的项，那么进行n次等式检查需要O(n)时间，其中n是项的数量。如果两个字典具有不同数量的项，则只需要O(1)时间，因为这两个字典肯定不同。请注意，等式检查可能会消耗大量计算资源。

一个问题是在估计时间复杂度时需要考虑到字典可以包含像列表、其他字典、树等值的情况。

例如，考虑以下两个字典：

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

这两个字典有相同的键，但为了检查列表是否相同，最坏情况下需要与列表大小成线性的时间。

然而，我们可以以需要进行比较的次数来讲。假设字典具有恒定的查找时间，那么需要比较n个元素的两个字典之间的比较次数为O(n)。

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

该函数首先会检查两个字典是否包含相同数量的对象。如果不是这种情况，则这两个字典肯定不相等。

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

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

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