len()函数的成本

Question

Python中的len()函数在处理内置数据类型（比如列表、元组、字符串和字典）时，耗费的时间和资源是多少呢？

Answer 1

这些对象都会记录自己的长度。提取长度的时间非常短（在大O表示法中是O(1)），主要的过程可以简单理解为：在一个字典里查找“len”这个关键词，然后把这个请求交给内置的len函数。这个函数会查找对象的__len__方法并调用它……实际上，它只需要做的就是return self.length，也就是返回这个对象的长度。

Answer 2

在官方的Python实现版本CPython中，对这些数据类型使用len()函数的时间复杂度是O(1)。这意味着无论数据的大小如何，计算长度所需的时间都是固定的，不会随着数据量的增加而增加。这里有一个链接，里面有很多不同函数在CPython中的算法复杂度的表格：

时间复杂度 Python维基页面

Answer 3

这段话的意思是，对于你提到的每种类型，操作的时间都是O(1)（也就是常数时间，不管元素的实际长度有多长，速度都很快）。这包括了set和其他一些，比如array.array。