python - 在 dictionary.values() 列表与集合中查找的时间复杂度

标签 python performance dictionary hashmap big-o

<分区>

在 Python 中，我们知道在字典中查找键需要 O(1) 运行时间，但在 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)。

如果值是集合，会是 O(N) 吗？

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}

平均情况 - 假设参数是随机均匀生成的 - 这种操作的时间复杂度为 O(n)

有关时间复杂度的更多信息，这里是 official link

关于python - 在 dictionary.values() 列表与集合中查找的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39380593/

上一篇：python - 子图和颜色的不同变量的 Pandas 图？

下一篇：python - 如何处理python scikit NMF中的缺失值

相关文章：

python - 使用 SciKit 在 python 中进行文档聚类

database - 小文件海量存储策略

java - 如何将自纪元以来的秒数转换为 Java 中的小时/分钟/秒？

c++ - 清除 map 和删除内容的最简洁方法是什么？

Python:从具有嵌套列表中的多个值的元组键制作字典

python - 从 C++ 调用 Python 或 Lua 来计算表达式，仅在需要时计算未知变量

python - 使用 xlrd 读取包含中文和/或印地语字符的 Excel xls 文件

mysql - 怎么可能有一个好的 EXPLAIN 和一个慢查询？

java - 如何将值放入 Map 内的 Map 中

python - PyGObject:无法控制进度条