java.util.TreeSet的tailSet操作的时间复杂度是什么？

Question

我正在使用sweepline实现2D最近点算法，该算法要求找到某个y坐标上方的六个点。我的做法是将这些点放入一个按y坐标排序的TreeSet中，并使用tailSet方法获取所有在某个点上方的点，并迭代至多6次。

我想知道tailSet操作的复杂度是否为O(log n)，如果是，那么在tailSet上迭代至多六次的复杂度也是O(log n)吗？

参考资料：http://people.scs.carleton.ca/~michiel/lecturenotes/ALGGEOM/sweepclosestpair.pdf

- Alvin John Burgos

Answer 1

据我所知，取tailSet的时间复杂度为O(log n)，但是迭代最后m个元素的时间复杂度为O(m * log n)。

- Peter Lawrey

---

哦，我明白了。迭代6次仍然是O(log n)。谢谢！现在我可以实现sweeplines:D 编辑：我以为按回车键会换行。 - Alvin John Burgos

@assylias，你说得对，这取决于你所讨论的操作。就你关心的那些操作而言，它可能是O(m)，但在导航成本方面，它更高。O(m * log n)是一个上限。 - Peter Lawrey

Answer 2

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

小澄清：tailSet()、headSet()和subSet()返回非常小的对象，它们将所有繁重的工作委托给底层集合的方法。没有构建新的集合。因此，时间复杂度为O(1)，并且相当微不足道。

讨论链接

- acridity