我想删除TreeSet中某个范围内的值,如下所示:
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i = 0; i < (int)1e7; i++){
ts.add((int)(Math.random() * 1e9));
}
System.out.println("ts: " + ts.size());
SortedSet<Integer> s = ts.subSet(500, (int)8e8);
s.clear();
System.out.println("ts: " + ts.size());
此操作的运行时间是多少?
它是O(log(n))
还是O(n)
?我发现一些references声明subSet()
操作需要log(n)
。我还读到clear()
操作是O(1)
,但单个节点不会被清除,使其可能是O(n)
吗?
1条答案
按热度按时间nx7onnlm1#
调用
TreSet#subSet
返回原始集合的 view。创建此视图是O(1)。创建子集视图时不复制任何元素。视图上的大多数操作都委托给基础的原始集合。但是
clear()
是个例外,在TreeSet
上调用clear
(实际上是TreeMap
)是O(1),因为它只将大小设置为0并清除根节点。这对于
TreeSet
的子集视图是不可能的,它需要逐个删除视图中的所有元素,委托给AbstractCollection#clear
方法,该方法的实现如下:从
TreeMap
的红黑树实现(其中TreeSet
仅仅是一个 Package 器)中移除单个条目是O(log(n))。因此,移除N个条目(需要为子集视图完成)是O(n * log(n))。