集合Java类树集合中的Java方法headSet和tailSet在日志(N)时间内工作吗?
JavaDoc中写到,树集上的基本操作在log(N)时间内工作,其中N是集合的大小。在我看来,如果集合足够大,headSet和tailSet方法应该通过类似二进制搜索的方式找到正在计算的视图的开始,但JavaDoc对此没有说明
你可以在下面搜索框中键入要查询的问题!
JavaDoc中写到,树集上的基本操作在log(N)时间内工作,其中N是集合的大小。在我看来,如果集合足够大,headSet和tailSet方法应该通过类似二进制搜索的方式找到正在计算的视图的开始,但JavaDoc对此没有说明
# 1 楼答案
文档没有提到
headSet
和tailSet
的时间复杂性。他们所说的是:(我强调的是查看)。而视图确实是最重要的部分。在最坏的情况下,创建视图总是一个
O(1)
操作,因为只创建包装类。不执行键搜索,只执行类型检查,实际上也不会触发其他操作下面是
TreeSet.headSet(E toElement)
代码:下面是
TreeSet.headSet(E toElement, boolean inclusive)
代码:您可能知道,
TreeSet
由一个TreeMap
实例支持。这就是m
属性的实际含义。因此,上面的操作将委托给TreeMap.headMap(E toElement, boolean inclusive)
方法,然后创建一个新的TreeSet
实例,该实例由TreeMap.headMap(E toElement, boolean inclusive)
返回的NavigableMap
实例支持首先,让我们看看
TreeSet
构造函数:如你所见,这只是一项任务
然后,让我们深入研究
TreeMap.headMap(E toElement, boolean inclusive)
方法的代码:这只是创建并返回
AscendingSubMap
静态嵌套类的实例。下面是AscendingSubMap
构造函数的代码:这只是委托给超类的构造函数(
AscendingSubMap
的超类是NavigableSubMap
静态嵌套抽象类)。下面是NavigableSubMap
构造函数的代码:如您所见,这只是检查参数的正确性并将其分配给属性
这里
m
是封闭的TreeMap
实例(请记住NavigableSubMap
是一个静态嵌套抽象类)。TreeMap.compare(Object k1, Object k2)
方法如下:这个方法只是适当地比较它的参数,这里它只是用来检查子映射的边界。(请记住
TreeMap
键可以是Comparable
也可以不是。如果不是,则在构造TreeMap
实例时必须提供Comparator
,这就是上面代码中的comparator
属性)这就是调用
headSet
方法时所做的一切tailSet
遵循相同的模式(只是最终子贴图的边界不同)因此,作为结论,
headSet
和tailSet
实际上是O(1)
最坏的情况强>注意:我已经检查了
JDK 8 v1.8.0_181
和openjdk version "11" 2018-09-25
版本的代码。我很确定中间版本也没有改变编辑:
关于访问由
headSet
返回的视图的第一个元素的时间复杂性,即如果要迭代它,则实现需要执行O(logN)
操作以到达TreeSet
的最左边的叶子(毕竟TreeSet
由TreeMap
支持,而TreeMap
又作为红/黑树实现)迭代
tailSet
返回的集合视图具有相同的时间复杂性:O(logN)
。这是因为实现需要对其值更接近所提供的下限的节点执行搜索,并且此搜索也是O(logN)