如果我有一个包含1000个元素的整数数组,那么查找特定元素索引的最快方法是什么?最好先对其进行QuickSort排序,然后使用BinarySearch还是只使用普通的老式LinearSearch?
另外,如果我有10万个元素,甚至只有100个元素,最快的方法会有所不同吗?
谢谢!
线性搜索会更好。O(N)
线性搜索的最坏情况少于单独的快速排序(平均,O(nlog n)
但最坏的情况O(N^2)
),然后您需要添加binarysearch(O(log N)
)。如果需要多次搜索,排序和使用二进制搜索会更好(如果您可以分摊排序成本,那么二进制搜索比线性搜索更有效)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句