Java 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());

时间复杂度拆解 #

1. subSet()操作：时间复杂度是O(log n)。TreeSet基于红黑树实现，这个方法仅需定位到范围的首尾节点（≥500的第一个节点、<8e8的前一个节点），红黑树的节点查找是对数级别的时间开销。
2. s.clear()操作：这里的clear()和普通TreeSet的O(1)清空逻辑不同——s是原TreeSet的视图而非独立副本，clear()需要删除原集合中所有落在[500, 8e8)范围内的元素。

整个组合操作的时间复杂度是**O(log n + k * log n)**，可简化为O(k * log n)，其中k是被删除的元素个数：

• 若k是常数级（比如仅删除少量元素），整体复杂度趋近于O(log n)；
• 若k和集合大小n同量级（比如范围覆盖了大部分元素），整体复杂度就是O(n log n)。

你之前查到的subSet()是O(log n)、普通clear()是O(1)的结论没错，但SubSet的clear()属于批量删除操作，复杂度和删除元素的数量直接相关，并非单纯的O(1)。

内容的提问来源于stack exchange，提问作者Abundance