Python3中x in range(n)的判断时间复杂度是多少？求官方文档参考

Great question! Let's clear this up once and for all, since it's a common point of confusion between Python 2 and 3.

核心结论 #

在Python 3中，x in range(n)的时间复杂度确实是O(1)，和Python 2.7的情况完全不同。

为什么和Python 2.7不一样？ #

你已经戳中了关键差异：Python 2.7里的range()会直接生成一个完整的列表，判断元素是否存在时需要遍历整个列表，时间复杂度是O(n)。而Python 3的range()返回的是一个range对象——这是一个专门的序列类型，它并不存储整个序列的所有元素，只保存start、stop、step三个核心参数。

当执行x in range(a, b, s)时，Python会通过简单的数学计算验证：

• x是否落在[start, stop)区间内（step为正）或(stop, start]区间内（step为负）
• (x - start)是否能被step整除

这些都是常数时间的操作，完全不需要遍历任何元素，所以时间复杂度是O(1)。

官方文档依据 #

Python官方文档中关于range类型的描述明确指出：

Membership testing for a range object is O(1) since it can be computed mathematically, instead of iterating through all elements of the range.

简单来说，成员检查是通过数学计算完成的，而非遍历，因此是常数时间。

直观验证小技巧 #

要是你想亲手感受差异，可以在Python 3里试试这段代码：

# 生成一个超大的range对象
big_range = range(10**18)
# 判断元素是否存在，瞬间完成
print(999999999999999999 in big_range)

这要是换成Python 2的range(10**18)，直接会因为内存不足报错，更别说遍历检查了。

内容的提问来源于stack exchange，提问作者user6794223