java - 如果我想在 arraylist 中搜索一个元素，那 Big-Theta 是什么？

Question

我想我可以先对数组进行排序，然后再使用二分查找。所以 O(n^2)。对吗？

Answer 1

I think I can sort the array first and then use binary search. So the O(n^2). Is that correct?

这种方法的复杂度对于排序来说是 O(nlogn)，对于二分搜索来说是 O(logn) 来进行查找。总体 O(nlogn)。

替代方法是简单的线性搜索查找(例如使用 contains 或循环)，时间复杂度为 O(n)。

排序和使用二进制搜索只会给你更好的性能，如果你可以分摊(整个列表)排序成本在大量查找上；即排序一次，搜索多次。

如果你想要比线性搜索更好，你需要使用一种数据结构，允许你更新排序结构¹ 优于 O(nlogn) 和搜索优于 O(n) .
最后......如果你这样做:

• 对初始数组列表进行排序。
• 通过使用二进制搜索找到插入/删除的正确点来更新排序的数组列表。
• 使用二进制搜索进行查找。

您最终将进行 O(n) 次更新操作(分摊 O(nlogn) 次排序步骤)和 O(logn) 次查找

---

简而言之，这是一组复杂的备选方案，最好的备选方案将取决于您的应用程序的预期行为。

---

^{1 - TreeSet 可以做到这一点(以消除重复项为模)。它在引擎盖下使用红黑二叉树。如果你的数据实际上是一个集合，那么你应该考虑 HashSet，它给你 O(1) 操作(除非哈希码函数是病态的)。}