在 dictionary.values() 列表与集合中查找的时间复杂度 [英] Time complexity for lookup in dictionary.values() lists vs sets

问题描述

在 Python 中，我们知道在字典中查找键需要 O(1) 运行时间，但是在 dictionary.values() 中查找的运行时间是多少?

In Python, we know that looking up a key in a dictionary takes O(1) run time, but what is the run time to look up in the dictionary.values() ?

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).

Edit #1: The values for the keys could be either lists or sets. Many folks have responded that if the values are lists the run time is O(1).

如果设置了值，它会是 O(N) 吗?

Will it be O(N) if values are sets?

dictionary = {'a':(66,77,88), 'b':(99,100)}
number = '99'
if number in dictionary.values():  # What is the run time here?

推荐答案

设x in s在一个列表中搜索的操作，{x=item , s=list}

Let be x in s the operation which searches in a list, {x=item , s=list}

平均情况 - 假设参数是随机均匀生成的 - 对于这样的操作将是 O(n)

The average case - assuming parameters generated uniformly at random - for such operation will be O(n)

有关时间复杂度的更多信息，请访问官方链接

For more info about time complexity, here's the official link

这篇关于在 dictionary.values() 列表与集合中查找的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！