В Python мы знаем, что поиск ключа в словаре занимает время O (1), но каково время выполнения поиска в словаре. значения() ?Сложность времени для поиска в словарях.values () lists vs sets
dictionary = {'a':[66,77,88], 'b':[99,100]}
key = 'a'
if key in dictionary: # takes O(1) run time
number = '99'
if number in dictionary.values(): # What is the run time here?
Редактировать # 1: Значения для ключей могут быть либо списками, либо наборами. Многие люди ответили, что если значения представляют собой списки, время выполнения - O (1).
Будет ли значение O (N), если значения заданы?
dictionary = {'a':(66,77,88), 'b':(99,100)}
number = '99'
if number in dictionary.values(): # What is the run time here?
'о (п)', конечно, как вы в худшем случае придется смотреть на каждое значение. Если использование python2 просто вызывает '.values ()' самостоятельно, создается список всех значений. –
O (n). Он читал все значения и сравнивал их с каждым из них. Кстати, это не сработает, если у вас есть списки как значения. – zvone
в основном это 'O (n)'. Но если вы хотите искать в таких значениях, которые являются списками, это не будет O (n). – Kasramvd