python - 集合上最小、最大的时间复杂度

Question

min, max 的时间复杂度为 O(N)，因为它们必须遍历给定的列表/字符串并检查每个索引以找到最小值/最大值。但我想知道如果在集合上使用 min,max 的时间复杂度是多少？例如:

s = {1,2,3,4} # s is a set

使用最小值/最大值我们得到:

min(s) = 1
max(s) = 4

由于集合不像列表和字符串那样使用索引，而是使用可以直接访问的桶进行操作，那么最小/最大的时间复杂度是否与一般情况不同？

谢谢!

Answer 1

正如上面的评论所指出的，python 是一种文档完善的语言，必须始终首先引用文档。

回答问题，根据docs ,

A set object is an unordered collection of distinct hashable objects.

无序意味着使用任何方法(内置或非内置)评估所有元素中的最大值或最小值至少需要查看每个元素，这意味着最多 O(n) 复杂度。

最重要的是，python 的 max 和 min 函数遍历每个元素，并且在所有情况下都是 O(n)。 您可以随时查找 source code自己。