如果我想搜索arraylist中的元素，那麼Big-Theta是什麼？

Question

我想我可以先排序數組，然後使用二分搜索。 所以O（n^2）。 這是正確的嗎？

Answer 1

我想我可以先排序數組，然後使用二分查找。所以O（n^2）。那是對的嗎？

該方法的複雜度爲O（nlogn），O（logn）爲二進制搜索進行查找。總體O（nlogn）。

另一種方法是簡單的線性搜索查找（例如使用contains或循環），它是O（n）。

如果您可以通過大量查找來分攤（整個列表）排序成本，則排序和使用二分查找只會提供更好的性能;即分類一次，搜索多次。

如果你想要比線性搜索更好，你需要使用一個數據結構，它允許你更新比O（nlogn）更好的搜索結果並且比O（n）更好地搜索結果。
最後...如果你這樣做：

• 排序初始arraylist。
• 使用二進制搜索來更新排序後的數組列表，以找到插入/刪除的正確點。
• 使用二進制搜索進行查找。

你將結束與O（N）更新操作（與O（nlogn）分選步驟攤銷）和O（logn）時間查找

---

總之，這是一個複雜的集替代品，最好的將取決於您的應用程序的預期行爲。

---

^{1 - 一個TreeSet會這麼做（模數，它消除重複）。它在引擎蓋下使用紅黑二叉樹。如果你的數據實際上是一個集合，那麼你應該考慮HashSet它給你O(1)操作（除非散列碼功能是病態的）。}