python - "in"的时间复杂度(包含运算符)

Question

我只是想知道何时理解像下面这样的算法的时间复杂度。

对于 python 列表，如果我们有一个 for 循环迭代它，然后进行包含检查，那么时间复杂度是否为 O(n^2)。

我知道两者都是 O(n)(或者我认为)，所以将它们嵌套在一起会使它变成 O(n^2) 吗？

我想如果这个“列表”真的是一个列表，那么下面这段代码的时间复杂度就是O(n^2)。但如果它是一本字典，它将是 O(n)，因为查找是 O(1)。对吗？

提前感谢您的帮助!

for element in list:
    if x in list:

Answer 1

你的分析是正确的。

• 列表包含是 O(n)，执行 O(n) 次 O(n) 次是 O(n²)。
• 字典查找的复杂度为 O(1)，执行 O(1) 次操作 O(n) 次的复杂度为 O(n)。