java - java.util.TreeSet的tailSet操作的时间复杂度是多少？

Question

我正在使用扫描线实现 2D 最接近对算法，它说您需要找到某个 y 坐标上方的六个点。我所做的是将点放入按 y 坐标排序的 TreeSet 中，并使用 tailSet 方法获取某个点以上的所有点，并迭代最多 6 次。

我想知道tailSet操作的复杂度是否为O（log n），如果是，是否最多迭代tailSet六次也是O（log n）？

score 5 · Accepted Answer

5

AFAIK采用tailSet是O（log n），但迭代最后一个m元素是O(m * log n)

于 2012-05-22T17:00:49.313 回答

score 3 · Accepted Answer

嗯...这对我来说很奇怪。我认为就大 O 而言，在 java.util.TreeSet 中创建 tailSet 的过程是 O(1)。

小说明：tailSet()、headSet() 和 subSet() 返回非常小的对象，它们将所有艰苦的工作委托给底层集合的方法。没有构建新的集合。因此 O(1) 并且非常微不足道。

2 回答 2