Python字典 len() 方法的时间复杂度

Question

例子：

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

<代码>len(a)的时间复杂度是什么？

- Yiling Liu

---

类似问题：https://dev59.com/G3NA5IYBdhLWcg3wC5NR - Hawkeye Parker

Answer 1

检查 dictobject.c 的 c 源代码，可以看到该结构体包含一个成员变量用于维护显式计数（dk_size）。

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

因此，它将具有顺序O(1)

- donkopotamus

Answer 2

根据这个网页:

时间复杂度: O(1) - 在Python中，变量被维护在容器内(这里是字典)，它持有容器的当前大小。因此，每当任何东西被推入或弹出容器时，变量的值就会递增(对于推入操作)/递减(对于弹出操作)。假设一个字典中已经存在2个元素。当我们向字典中插入另一个元素时，持有字典大小的变量的值也会随之递增，因为我们插入了该元素。它的值变成3。当我们在字典上调用len()函数时，它调用了魔法函数len()，它只返回大小变量。因此，这是O(1)操作。

空间复杂度: O(1) - 由于只有一个变量持有字典的大小，因此没有辅助空间涉及。因此，该方法的空间复杂度也是O(1)。

- Yiling Liu

---

你应该将这段内容放在引用块中，以便清楚地表明这不是你自己的写作。 - donkopotamus