python - Python3 中字典的空间复杂度

Question

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

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

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

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

(2) 我的猜测:O(V) 其中 V 是 key 的数量。

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

Answer 1

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

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

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

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