Сложность времени Python словарь метод len ()

Question

Пример:

a = {a:'1', b:'2'}
len(a)

Какова временная сложность len(a)?

Answer 1

Проверка c -источника dictobject.c показывает, что в структуре содержится член, отвечающий за поддержание явного подсчета (dk_size)

layout:
+---------------+
| dk_refcnt     |
| dk_size       |
| dk_lookup     |
| dk_usable     |
| dk_nentries   |
+---------------+
...

Таким образом, он будет есть заказ O(1)

Answer 2

Согласно этой странице :

Сложность времени: O (1) - В Python переменная поддерживается внутри контейнера ( здесь словарь), который содержит текущий размер контейнера. Таким образом, всякий раз, когда что-либо помещается или выталкивается в контейнер, значение переменной увеличивается (для операции pu sh) / уменьшается (для операции pop). Допустим, в словаре уже есть 2 элемента. Когда мы вставляем другой элемент в словарь, значение переменной, содержащей размер словаря, также увеличивается, когда мы вставляем элемент. Его значение становится равным 3. Когда мы вызываем len () в словаре, он вызывает функцию magi c len (), которая просто возвращает переменную размера. Следовательно, это операция O (1).

Сложность пространства: O (1) - Поскольку существует только одна переменная, содержащая размер словаря, вспомогательное пространство не используется. Следовательно, пространственная сложность метода также равна O (1).