检查列表时Python“if x in y”的最佳时间复杂度[重复]

Question

我正在分析我编写的一些代码的最佳和最差时间复杂度。我已经被困了一段时间，试图理解 python

if x in y

最佳时间复杂度是什么，因为我没有找到很多资源提到它。 我的理解是，在最好的情况下

list = [3, 1, 4, 5, 7]

，元素

3

将在恒定时间内被检索，因为它存在于列表的开头。

Answer 1

您的理解是正确的。在 Python 中，列表的

in

运算符的平均时间复杂度为 O(n) [n 列表大小]。但是，最好的情况是，如果您要搜索的元素是列表中的第一个元素，则时间复杂度将为常数时间，即 O(1)。这是因为 Python 列表是作为动态数组实现的，当您使用

in

时，Python 会线性迭代列表，直到找到元素或到达列表末尾。

最好的情况[第一个元素] -> O(1) 平均情况或最坏情况：O(n)

这仅适用于Python中的列表，不适用于任何其他数据结构