在Python元组中检查成员资格的时间复杂度是多少？

Question

在此处列出用于检查字典，列表和集合中的成员资格（x in data_structure）的时间复杂度：http://wiki.python.org/moin/TimeComplexity

• dict-O（1）
• 列表-O（n）
• set-O（1）

但是，我在任何Python文档中都找不到元组。我尝试了以下代码进行自我检查：

import time 

l = list(range(10000000))
t = tuple(range(10000000))
s = set(range(10000000))

start = time.perf_counter()  
-1 in s
elapsed = time.perf_counter() 
e = elapsed - start 
print("Time spent in set is: ", e)

start = time.perf_counter()  
-1 in l
elapsed = time.perf_counter() 
e = elapsed - start 
print("Time spent in list is: ", e)


start = time.perf_counter()  
-1 in t
elapsed = time.perf_counter() 
e = elapsed - start 
print("Time spent in tuple is: ", e)

我得到这样的东西：

Time spent in set is:  2.0000000000575113e-06
Time spent in list is:  0.07841469999999995
Time spent in tuple is:  0.07896940000000008

这告诉我也是O（n）。有人可以确认吗？是否有官方文件确认这一点？

Answer 1

将元组视为“只是冻结列表”。当然，还有更多细节，但是最后一个元组就像一个列表列表，其中包含一组条目，必须逐个进行搜索才能找到objevt是否是该元组的成员。

因此，成员资格测试的复杂度与列表相同。

是O（n）