3

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

我想知道tailSet操作的复杂度是否为O(log n),如果是,是否最多迭代tailSet六次也是O(log n)?

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

4

2 回答 2

5

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

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

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

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

讨论链接

于 2012-10-20T08:39:53.677 回答