查找数组长度的时间复杂度

Question

我对len()函数的时间复杂度感到困惑。

我读过许多不同的文章，发现在python中查找数组的长度O(1)与该len()函数有关，其他语言也类似。

这怎么可能？您是否不必遍历整个数组来计算它占用了多少索引？

Answer 1

您是否不必遍历整个数组来计算它占用了多少索引？

你不可以。

通常，在构造算法时，您总是可以将空间换为时间。

例如，在创建集合时，分配一个单独的变量来保存大小。然后在将项目添加到集合中时增加该值，而在删除某些项目时减少它。

然后，O(1)只需访问该变量即可及时获得集合的大小。

并指出，这似乎是Python实际执行的操作（如本页所示）（检查Python源代码显示，这是请求大量对象的大小时的动作）：

Py_SIZE(o)-此宏用于访问ob_sizePython对象的成员。它扩展为(((PyVarObject*)(o))->ob_size)。