如果我想在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)的搜索.
最后......如果你这样做:

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

简而言之,它是一组复杂的替代方案,最好的方案取决于应用程序的预期行为.

^{1 - A TreeSet会这样做(模数消除重复).它使用引擎盖下的红黑二叉树.如果您的数据实际上是一个集合,那么您应该考虑HashSet哪个为您提供O(1)操作(除非哈希代码函数是病态的).}