查找元素是否存在于未排序数组中的最快方法？ [英] Fastest way to find if element exists in an unsorted array?

问题描述

用于搜索未排序数组以进行元素线性搜索的最快算法是吗？我的意思是我想合并排序+二进制搜索的组合会更慢。还有其他选择吗？ （就不涉及多线程的算法而言）？

Is the fastest algorithm for searching an unsorted array for an element linear search? I mean I guess a combination of merge sort + binary search would be slower. Are there any other options? (in terms of algorithms not involving multithreading)?

推荐答案

是的，如果数组是未排序的，那么您就知道它的结构了那么搜索元素的最快方法就是考虑每个花费线性时间 O（n）的元素。

Yes, if the array is unsorted and that's all you know about its structure then the fastest way to search for an element is to consider every one which takes linear time O(n).

要搜索大量数组，则可能需要考虑进行初始排序，然后将元素插入其正确的排序索引中（使用二进制搜索）。这意味着您的初始排序为 O（n log n），但是每次插入和搜索都需要 O（log n）。这都是权衡因素，它是否比 O（1）插入和 O（n）搜索更好。

If you are going to be searching the array a lot then you may want to consider an initial sort and then insert elements into their correct sorted index (using binary search). This means that you have your initial sort as O(n log n) but each insert and search takes O(log n). It's all about tradeoffs and whether that is better than O(1) insert and O(n) search.

您说过不使用多线程，但这是提高性能的一种简便方法，让多个线程查看列表中的不同块。

You said no multithreading but that is an easy way to boost performance, have multiple threads look at different chunks in the list.

这篇关于查找元素是否存在于未排序数组中的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！