6

オブジェクトのコレクションがあるとします:

List<String> myList = populateMyArrayList();
//Here I am having an ArrayList with 1000 elements

どちらがより良いアプローチですか：

1 : マージソートしてから二分探索

Collections.sort(myList);
int keyIndex = Collections.binarySearch(myList, key);

2 : 順次検索

for(String s : myList){
   if(s.equals(key)){
      return s;
   }
}

検索するコレクションのサイズに基づいて、検索アプローチに違いがあるはずですか? はいの場合、どのように決定するか。

EDIT1:リストを数回検索する必要があり、リストに新しい要素が追加されないとします。

EDIT2:を選択することもできましたがHashSet、実際には を使用しており、CustomObject のさまざまな属性に基づいList<CustomObject>て複数回検索できます。したがって、CustomObject にListオーバーライドされたメソッドを含めることはできませんequals

4

4 に答える 4

4

検索を 1 回だけ行う場合:

  • ソート + 二分探索の複雑さは になりますO(n * log n)。
  • 線形検索の複雑さは ですO(n)。

複数回検索する場合は、次のようにしますk。

  • ソート + 二分探索の複雑さは になりますO((n + k) * log n)。
  • 線形検索の複雑さは になりますO(k * n)。

したがって、検索を 1 回だけ行う場合は、線形検索を使用する必要があります。検索を複数回行う場合は、最初にソートする必要があります。

また、この場合O(1)、要素検索の複雑さを償却したハッシュ テーブルの使用を検討することもできます。

于 2014-05-26T11:15:21.893 に答える