具有多个if语句的嵌套for循环的时间复杂性

Question

在这种情况下，理想的时间复杂度是多少？

For i in list1:
If i in list2:
If i not in list3:
i.append(list)

提前感谢

Answer 1

时间复杂性取决于数据结构列表1-3及其内容的实现。假设您有一个需要完全遍历才能执行x in list语句的列表：

For i in list1: // O(n) where n is the length of list1
If i in list2: // O(n*m) where m is the length of list2
If i not in list3 // O(n*m*o) where o is the length of list3

最坏的情况是，如果i是否在list3上，则任何i in list2为true都将导致O(n*m*o)独立，因为您必须以任何方式检查完整的list3，并且依赖if的附加值是常量。

在最好的情况下，任何i in list2为false都将导致O(n*m)，因为您不必执行list3迭代的任何代码。