更快的方法是:先使用Quicksort,然后使用二元搜索还是线性搜索?

26hmkk:

如果我有一个包含1000个元素的整数数组,那么查找特定元素索引的最快方法是什么?最好先对其进行QuickSort排序,然后使用BinarySearch还是只使用普通的老式LinearSearch?

另外,如果我有10万个元素,甚至只有100个元素,最快的方法会有所不同吗?

谢谢!

艾略特·弗里施(Elliott Frisch):

线性搜索会更好。O(N)线性搜索的最坏情况少于单独的快速排序(平均,O(nlog n)但最坏的情况O(N^2)然后您需要添加binarysearch(O(log N))。如果需要多次搜索,排序和使用二进制搜索会更好(如果您可以分摊排序成本,那么二进制搜索比线性搜索更有效)。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章