Сложность пространства для словаря в 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).