min, max have O(N) time complexity because they have to loop over the given list/string and check every index to find min/max. But I am wondering what would be the time complexity of min,max if used on a set? For example:
min,max具有O(N)时间复杂度,因为它们必须遍历给定的列表/字符串并检查每个索引以找到min / max。但我想知道如果在一组上使用min,max的时间复杂度是多少?例如:
s = {1,2,3,4} # s is a set
using min/max we get:
使用min / max得到:
min(s) = 1
max(s) = 4
Since sets do not use indices like lists and strings, but instead operate using buckets that can be accessed directly, does the time complexity of min/max differ than the general case?
由于集合不使用列表和字符串之类的索引,而是使用可以直接访问的存储桶来操作,因此min / max的时间复杂度是否与一般情况不同?
Thank you!
1 个解决方案
#1
0
As pointed out in the comments above, python is a well documented language and one must always refer to the docs first.
正如上面的评论中所指出的,python是一种记录良好的语言,必须始终首先引用文档。
Answering the question, according to the docs,
根据文件回答这个问题,
A set object is an unordered collection of distinct hashable objects.
set对象是不同的可哈希对象的无序集合。
Being unordered means that to evaluate maximum or minimum among all the elements using any means (inbuilt or not) would at least require one to look at each element, which means O(n) complexity at best.
无序意味着使用任何方法(内置或非内置)评估所有元素中的最大值或最小值至少需要一个人查看每个元素,这意味着O(n)复杂度最多。
On top of it, max and min functions of python iterate over each element and are O(n) in all cases. You can always look up the source code yourself.
最重要的是,python的max和min函数遍历每个元素,并且在所有情况下都是O(n)。您始终可以自己查找源代码。
#1
0
As pointed out in the comments above, python is a well documented language and one must always refer to the docs first.
正如上面的评论中所指出的,python是一种记录良好的语言,必须始终首先引用文档。
Answering the question, according to the docs,
根据文件回答这个问题,
A set object is an unordered collection of distinct hashable objects.
set对象是不同的可哈希对象的无序集合。
Being unordered means that to evaluate maximum or minimum among all the elements using any means (inbuilt or not) would at least require one to look at each element, which means O(n) complexity at best.
无序意味着使用任何方法(内置或非内置)评估所有元素中的最大值或最小值至少需要一个人查看每个元素,这意味着O(n)复杂度最多。
On top of it, max and min functions of python iterate over each element and are O(n) in all cases. You can always look up the source code yourself.
最重要的是,python的max和min函数遍历每个元素,并且在所有情况下都是O(n)。您始终可以自己查找源代码。