python - 常数数组大小的时间复杂度

Question

使用以下 python 程序从 fruits 中“过滤”出 banned_fruit:

banned_fruit = {"apple", "orange", "grape"} # always size = 3
fruits = ["banana", "apple", "blueberry", "kiwi", "orange"]  # size = N

good_fruit = []
for fruit in fruits: # O(N)
    if fruit not in banned_fruit: # O(1) average case, worst case O(3) = O(1) ?
        good_fruit.append(fruit) 

print(good_fruit) # Output: ['banana', 'blueberry', 'kiwi']

我的问题是上述程序在最坏情况下的时间复杂度是多少？令我困惑的是这条线:

if fruit not in banned_fruit:

如果 banned_fruit 是一个 python 集，那么根据我的理解，它的最坏情况时间复杂度可能为 O(K) 其中 K 是 banned_fruit 集的长度。但是，如果 banned_fruit 集的长度始终不变(即:3)，这是否意味着最坏的情况将是 O(1) 从而使我的整个程序时间复杂度为 O(N)，还是我需要考虑集合的搜索时间，使我的时间复杂度为 O(NK)？

Answer 1

复杂性理论是关于程序的时间或空间如何根据可变大小的输入而变化。

如果算法的一部分使用固定大小的对象，那么这不是您在确定复杂性时要考虑的变量。如果集合大小是预定义的而不是可变的，则不会影响算法的复杂性。