python 'in' 运算符对各种数据类型的访问时间是多少？

Question

正如标题所说，我想知道 'in' 运算符对于各种数据结构的速度有多快。例如，对于字典，由于字典充当哈希映射，我知道访问时间是摊销常数，O(1)。

在列表或字符串中的子字符串中呢？

5 in [1,2,3,4,5]
'hello' in 'hello world'

我的直觉告诉我这些将是 O(n) 的访问时间，但也许在列表的情况下，也许 python 支持带有散列集的列表元素以加速该过程。

Answer 1

时间复杂度记录在 Python wiki。

列表成员测试需要O(n)的时间；这同样适用于任何序列类型（因此字符串也是 O(n)）。对于集合和字典，成员资格测试是 O(1) 常数时间。