len是O(1)，因为在RAM中，列表存储为表(一系列连续的地址)。要知道表何时停止，计算机需要两个东西:长度和起点。这就是为什么len()是O(1)，计算机存储值，所以它只需要查找它。

下面的测量结果证明，对于常用的数据结构，len()为O(1)。

关于timeit的注意事项:当使用-s标志并将两个字符串传递给timeit时，第一个字符串只执行一次，并且不计时。

列表:

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

元组:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

字符串:

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

字典(Dictionary -comprehension在2.7+中可用):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

数组:

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

Set (Set -comprehension在2.7+中可用):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

发现:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

所有这些对象都记录自己的长度。提取长度的时间很短(大O表示法中的O(1))，主要由[粗略描述，用Python术语编写，而不是C术语]组成:在字典中查找“len”并将其分派给内置len函数，该函数将查找对象的__len__方法并调用它…它所要做的就是返回self。length

在这些数据类型上调用len()是CPython中的O(1)， CPython是Python语言的官方和最常见的实现。这里有一个表的链接，它提供了CPython中许多不同函数的算法复杂度:

TimeComplexity Python Wiki页面

它是O(1)(常数时间，不依赖于元素的实际长度-非常快)对于你提到的每一种类型，加上set和其他如array.array。

len是O(1)，因为在RAM中，列表存储为表(一系列连续的地址)。要知道表何时停止，计算机需要两个东西:长度和起点。这就是为什么len()是O(1)，计算机存储值，所以它只需要查找它。