33

一緒に追加すると、探している別の値になる値のペアを探すアルゴリズムを書いています。

a を使用するMapと、アルゴリズムが O(n²) から高速化されることがわかりました。私は後で、 my に含まれる値を実際には使用していないことに気付きましMapたList。

Google でパワー検索を行いましたが、質問のタイトルにあるこれらのメソッドの漸近的な実行時間に関する情報は見つかりませんでした。

そのような情報をどこで探すべきか教えていただけますか?

4

4 に答える 4

58

私は後で、 my に含まれる値を実際には使用していないことに気付きましMapたList。

Mapキーと値のペアの単なるリストではなく、キーから値への一意のマッピングです。したがって、 からMapに変更するとList、以前はできなかった重複が許可されます。一方、 aSetは値なしで正確に aMapです。したがって、を使用することを検討してHashSetください。

検索の複雑さについては、次のとおりです。

list.containsは O(n)、hashSet.containsO(1)、treeSet.containsO(log n) です。

now works の一般的な情報についてはHashMap、「hashtable」でググってください。についてTreeMapは、「バイナリ ツリー」などをググってください。ウィキペディアには、これらの主題に関する優れたエントリがあります。

ただし、 class を避けるように注意してくださいHashtable。これは、現代の図書館にある考古学的遺物です。あなたの場合HashSet、おそらく最良の選択です。

于 2012-07-23T13:23:52.323 に答える
6

MapとListはインターフェイスであるため、実装やパフォーマンスに関する情報はありません。ただし、最新の実装 (LinkedListまたはArrayListfor List、およびHashMapfor Map) を使用する場合、contains()メソッドは、最悪の場合、リスト全体を調べて、要素を各エントリと比較する必要があります。これは O(n) 操作です。

を使用する場合HashMap、実装は根本的に異なります。 にHashMapは、要素よりも多くのエントリを持つ配列が含まれます (実際には、マップ内の n 要素に対して 4n/3 から 3n/2 の配列サイズがあります)。int であるキーのハッシュを計算し、0 と配列サイズの間でラップします (この数値が であるとしましょうi)。次に、要素をi配列のインデックスに配置します（またはi+1、i+2前のインデックスが既に取得されている場合は…）。そのため、 でキーの存在をチェックすると、ハッシュと値containsKeyが再計算され、空の配列セルが見つかるまで, … インデックスがチェックされます。理論的には、O(n) の最悪のケースを持つことができます。配列がほぼ満杯の場合、すべてのキーがほぼ同一です。iii+1i値ですが、優れたハッシュ関数を使用すると、定数時間containsとget関数が得られます。（ただし、配列のサイズを変更する必要がない場合、要素の追加は高速です。これは非常に遅いです-各キーのインデックスを再計算する必要があると思います）。

したがって、コレクション内のキーの外観を確認する必要があり、順序を維持する必要がない場合 (そのための がありますが、SortedHashMapパフォーマンスについてはわかりません)、マップは本当に高速ですが、より多くのメモリが必要になります。

また、キー値が必要ない場合は、HashSet(内部的には と同じですHashMap) を使用できます。

于 2012-07-23T13:40:55.677 に答える
0

Map.containsKey（）は、HashMapでの検索がO（1）で行われるため、HashMapを使用していることを考慮しています。

List.contains（）は通常、順次検索またはバイナリ検索に頼る必要があるため、複雑さは少なくともO（log n）になります。

于 2012-07-23T13:25:10.873 に答える