"时间复杂度 - 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

你的分析是正确的。在

• List containment是O（n），执行O（n）操作O（n）次是O（n²）。在
• 字典查找是O（1），执行O（1）操作O（n）次是O（n）。在