“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)。