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：我本可以选择 a HashSet，但实际上我有 aList<CustomObject>并且我可以List根据 CustomObject 的不同属性多次搜索。equals所以我的 CustomObject中不能有被覆盖的方法

4

4 回答 4

14

这取决于。

  • 如果您只搜索一个字符串，则线性搜索会更好，因为它位于O(n)
  • 如果您要搜索多个字符串，首先排序然后二进制搜索可能会更好。它将是O(logn + n*logn)哪个O(n*logn)。因此，如果您正在检查 ca。n弦，这个更好。
  • 如果您只想知道您的 Collection 是否包含一个元素（忽略顺序），您应该考虑使用HashSetwhich has O(1)。
  • 如果您需要订购和快速包含方法，请使用LinkedHashSet

PS过早优化是万恶之源。

于 2014-05-26T11:11:26.407 回答
4

如果您只进行一次搜索：

  • 排序+二分查找的复杂度为O(n * log n).
  • 线性搜索的复杂度是O(n)。

如果您进行多次搜索，假设是k次：

  • 排序+二分查找的复杂度为O((n + k) * log n).
  • 线性搜索的复杂度为O(k * n)。

因此，如果您只进行一次搜索，您应该使用线性搜索。如果您进行多次搜索，很可能您应该首先进行排序。

此外，也许在这种情况下，您可以考虑使用哈希表，它具有O(1)元素搜索的分摊复杂性。

于 2014-05-26T11:15:21.893 回答
0

如果您只搜索列表一次（或很少）线性搜索更便宜。如果您更频繁地搜索列表，则可以偿还排序成本。排序成本 O(n log n) 平均时间复杂度和搜索然后 O(log n)。如果您搜索几乎“每个元素”，这也会花费 O(n) 平均时间复杂度，并且您在排序方面是“偶数”。

于 2014-05-26T11:11:02.410 回答
0

二进制搜索是 O(log(m)) 并且比 O(n) 的线性搜索要快。然而，必须首先对数据进行排序：O(n log(n))，这需要更长的时间。

因此，如果数据填充一次，然后经常寻找，请进行排序和二进制搜索。更好的是：拿一套。HashSet会更好。

于 2014-05-26T11:12:21.920 回答