Python3 中字典的空间复杂度

Question

Python中这个字典的空间复杂度是多少？

(1)我的猜测：O(V+E)，其中V是键的数量，E是字典中数组值的最大长度。

{
    'key' : ['value', 'value2', ...],
    'key2': ['value30', 'value31', ...],
    ...
}

小问题：如果字典是由有向图构成的，那么它的空间复杂度应该是O(2E)吗？

(2)我的猜测：O(V)，其中V是密钥的数量。

{
    'key' : 4,
    'key2': 5,
    ...
}

Answer 1

Python 中的字典是作为哈希表实现的。

通常，哈希表有 n 个键和 n 个元素（每个键一个）。这将使它们具有 O(n) 空间，因为我们可以在 O(2n) 中删除常量。

您想要做的是采用像数据结构这样的哈希表，并让它表现出通常不会的行为...我理解您尝试使用它的方式是您有元素列表，每个列表可以通过关键。由于每个列表可以有自己的长度，所以空间复杂度的更好表示是 O(k + v1 + v2... + vn)，其中 v1 是列表 1 的长度，vn 是最后一个列表的长度。

如果您像使用哈希表一样使用字典，则空间复杂度为 O(n)。