3

スイープラインを使用して2D最接近ペアアルゴリズムを実装していましたが、特定のy座標の上の6つのポイントを見つける必要があると表示されます。私が行ったのは、ポイントをy座標でソートされたTreeSetに配置し、tailSetメソッドを使用して、特定のポイントより上のすべてのポイントを取得し、最大6回反復することです。

tailSet操作の複雑さがO（log n）であるかどうか疑問に思いました。そうである場合、tailSetを最大で6回繰り返しますか？O（log n）？

参照： http： //people.scs.carleton.ca/~michiel/lecturenotes/ALGGEOM/sweepclosestpair.pdf

4

2 に答える 2

5

AFAIKテールセットの取得は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 に答える