未排序列表与线性和二分搜索

Question

大家好，我一直在为即将到来的考试而学习，我遇到了这个问题：

如果您有一个包含 100 万个唯一项的未排序列表，并且知道您只会为一个值搜索它一次，那么以下哪种算法最快？

1. 在未排序列表上使用线性搜索

2. 使用插入排序对列表进行排序，然后对排序后的列表进行二分查找

第二个选择不是最快的吗？排序列表然后查找值而不是仅使用线性搜索？

Answer 1

线性搜索只需要O(n)，而对列表进行排序首先需要O(n log n)。由于您将只在列表中搜索一个值，因此使用二分搜索在排序列表中进行后续搜索仅需要O(log n) 的事实无助于克服O(n log n)时间复杂度的开销参与排序，因此线性搜索对任务更有效。

Answer 2

对列表进行排序O(log(N)*N)充其量具有复杂性。线性搜索具有O(N)复杂性。因此，如果您必须多次搜索，则在进行一些搜索后，您就会开始获得时间。如果对象是可散列的（例如：整数），排序+二分搜索的一个不错的替代方法（仅搜索多次时）是将它们放在set. 然后复杂性归结为O(1)散列，但仍然O(N)要创建它，而散列会增加损失。如果只需要搜索一次，线性搜索是最好的选择。