关于不同数据结构（列表、元组、集合和字典）的查找速度的问题

Question

我尝试使用 timeit 进行计时

if x in

来测试列表、元组、字典和集合之间的差异。

输入：

arr = [45,42,2,18,23,1170,12,41,40,9,47,24,33,28,10,32,29,17,46,11,759,37,6,26,21,49,31,14,19,8,13,7,27,22,3,36,34,38,39,30,43,15,4,16,35,25,20,44,5,48]
d = {x: None for x in arr}
s = set(arr)
t = tuple(arr)

print(timeit.timeit(stmt="1170 in arr",globals = globals()))
print(timeit.timeit(stmt="1170 in d",globals = globals()))
print(timeit.timeit(stmt="1170 in s",globals = globals()))
print(timeit.timeit(stmt="1170 in t",globals = globals()))

输出：

0.04749280004762113
0.03289399994537234
0.02820739999879152
0.05428230005782098

我在网上读到，集合和字典的查找是 O(1)，而元组和列表的查找是 O(n) 或最多 O(log n)。

我的问题是：

• 为什么集合/字典是 O(1)，而列表/元组是 O(n)？
• 为什么集合比字典更快，两者都是 O(1) ？
• 当元组和列表都是 O(n) 时，为什么元组比列表慢？

编辑： 如果我查找不在数据结构中的项目，例如 9999（按照 Andrej Kesely 的建议），我会观察到字典始终比集合快，而列表仍然比元组稍快。

输出：

0.2764877999434248
0.0286063000094146
0.0490725999698043
0.3088887999765575

Answer 1

Big-O 表示法通常用于表示算法的效率。它纯粹是从理论角度出发，并受到操作流程的限制，而不是实际时间。由于问题的具体情况，使用 Big-O 时，算法的优化版本有可能获得更差的评级，尽管不太可能。 O(1) 意味着该操作将始终花费恒定的时间。 O(n) 意味着操作将花费一定的时间，该时间与正在操作的元素的数量直接相关。 O(log n) 通常是可实现的最快算法。

字典是常数时间（O(1)），因为它们本质上提供了一个从输入值获取整数的函数，并且该整数基本上用作数组索引。因此占用了巨大的内存区域，但是如果您使用键从该哈希函数生成索引，则立即给出结果。

Set，我还没有确定，但考虑一下它们......可能它们只是字典，其值被初始化为 false 或其他值的布尔值。

通过列表或元组线性搜索是 O(n)，因为您从左到右。访问列表或元组也是 O(n)，但是当您知道数组的索引时，访问数组的时间复杂度为 O(1)（值得注意的是，并非所有列表都相同，但这是针对未优化的链表）。

我所知道的一切都说元组应该更快，除非你在功能上修改它而不是改变列表？我不太明白这个，如果有人评论我会更新。