Временная сложность постоянного размера массива

Question

Возьмите следующую программу на Python, которая "отфильтровывает" banned_fruit из fruits:

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 - это набор питонов, то, насколько я понимаю, он может иметь сложность времени в худшем случае O(K), где K - этодлина набора banned_fruit.Но если длина набора banned_fruit всегда постоянна (т. Е. 3), это будет означать, что наихудшим случаем будет O(1), поэтому моя общая программа будет иметь сложность по времени O(N), или янужно учитывать время поиска набора, делая мою сложность времени O(NK)?

Answer 1

Теория сложности заключается в том, как время или пространство программы изменяется в зависимости от входных данных переменного размера.

Если часть алгоритма использует объект фиксированного размера, это не та переменная, которую вы учитываете при определениисложностьЕсли заданный размер задан заранее, а не может варьироваться, это не влияет на сложность алгоритма.

Answer 2

Сложность времени будет O (N).В наихудшем случае сложность поиска набора будет O (длина набора), если существует слишком много коллизий хэшей, которые могут произойти, если множество элементов в хэше набора имеют одно и то же значение.Так что в вашем случае это будет O (N) [сложность вашего цикла] практически [размер вашего набора постоянен], и вам не нужно называть его O (NK).