TreeSet のいくつかの操作の複雑さに関するいくつかのことを解決しようとしています。javadoc には次のように書かれています。
「この実装は、基本的な操作 (追加、削除、および含む) の保証された log(n) 時間コストを提供します。」
ここまでは順調ですね。私の質問は、addAll()、removeAll() などで何が起こるかです。ここで Set の javadoc は次のように述べています。
「指定されたコレクションもセットである場合、addAll 操作はこのセットを効果的に変更し、その値が 2 つのセットの結合になるようにします。」
操作の論理的な結果を説明しているだけですか、それとも複雑さについてのヒントを提供していますか? つまり、2 つのセットがたとえば赤黒の木で表されている場合、一方の要素を他方の要素に「追加」するよりも、どうにかして木を結合する方がよいでしょう。
いずれにせよ、2 つの TreeSet を O(logn) の複雑さで 1 つに結合する方法はありますか?
前もって感謝します。:-)
特殊なケースを に最適化する方法を想像できますO(log n)が、最悪のケースは、各ツリーの要素の数とO(m log n)場所です。mn
編集：
http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm
ツリーを結合できる特殊なケースのアルゴリズムについて説明しますO(log(m + n))が、制限に注意してください: のすべてのメンバーは のS1すべてのメンバーより小さくなければなりませんS2。これは、特別な場合には特別な最適化があるという意味です。
TreeSet の Java ソースを見ると、渡されたコレクションが SortedSet の場合、O(n) 時間アルゴリズムを使用しているように見えます。それ以外の場合は、super.addAll を呼び出します。これにより、O(n logn) が発生すると思います。
編集-コードを読むのが速すぎると思います.TreeSetは、バッキングマップが空の場合にのみO(n)アルゴリズムを使用できます
このブログ投稿によると:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
O(n log n) です。ドキュメントには複雑さについてのヒントがないため、パフォーマンスが重要な場合は、独自のアルゴリズムを作成することをお勧めします。
2 つのツリーの要素が互いに素であるかどうかがわからないため、ディスジョイント セットのデータ構造のように、ツリーのマージやセットの結合を実行することはできません。データ構造には他のツリーのコンテンツに関する知識があるため、ある要素が他のツリーに存在するかどうかを確認してから、要素を追加するか、少なくとも別のツリーに要素を追加しようとし、見つかった場合は追加を中止する必要があります。道。したがって、O(MlogN) である必要があります。