min、max 的时间复杂度为 O(N),因为它们必须循环给定的列表/字符串并检查每个索引以找到最小值/最大值。但我想知道如果在集合上使用 min,max 的时间复杂度是多少?例如:
s = {1,2,3,4} # s is a set
使用最小/最大我们得到:
min(s) = 1
max(s) = 4
由于集合不使用列表和字符串等索引,而是使用可直接访问的存储桶进行操作,那么 min/max 的时间复杂度与一般情况是否有所不同?
谢谢你!
正如上面的评论所指出的,Python 是一种文档齐全的语言,必须始终首先参考文档。
回答问题,根据docs https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset,
集合对象是不同的可哈希对象的无序集合。
无序意味着使用任何方法(内置或非内置)评估所有元素中的最大值或最小值至少需要查看每个元素,这意味着最多 O(n) 复杂度。
最重要的是,Python 的 max 和 min 函数迭代每个元素,并且在所有情况下都是 O(n)。
您可以随时查找源代码 https://hg.python.org/cpython/file/de17b0cf1a20/Python/bltinmodule.c#l1260你自己。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)