在二元搜索之前完成排序时的时间复杂度...请参阅

Question

假设有一个包含未排序数据的数组,我需要选择线性搜索或二进制搜索进行搜索.然后我应该选择哪个选项？线性搜索的时间复杂度为O(n),二进制搜索的时间复杂度为O(log n).但是,最快的排序算法给出了O(n*log n)的时间复杂度.现在,我不知道如何"添加"两种算法的复杂性(如果这是正确的词),因此,我问这个问题.

所以我的问题是,如果排序然后二元搜索比简单的线性搜索更好,还是另一种方式？

另外,如何使用大O表示法(我的意思是"添加"和"比较"时间复杂度)来证明任何情况？

非常感谢您的阅读!!!那意义重大.

Answer 1

你并没有真正"添加"复杂性.正如你所说的那样,排序是O(n*log n),搜索是O(log n).如果你要对它们进行"正常数学运算",那么它将是(n + 1)*log n,它仍然是n*log n.

当您执行这样的多个步骤时,通常会采用最高的复杂性并将其称之为.毕竟,当n足够大时,n*log n使log n变矮.

可以这样想:当n为1,000,000时,n*log n为2000万.log n是20.那么20,000,000和20,000,020之间有什么区别？(log n)术语无关紧要.因此,对于所有意图和目的,(n log n)+(log n)等于(n log n).即使n为100,log n也是7.当n甚至中等大时,(log n)项也不会产生差异.

在您的特定情况下,如果您只需要搜索一次列表,那么顺序搜索就是您的选择.如果你需要多次搜索,那么你必须权衡m搜索O(m*n)的成本与排序和搜索的成本.如果您对最短时间感兴趣并且您知道要搜索列表的次数,那么如果(m*n)小于(n*log n),则使用顺序搜索.否则使用排序然后二进制搜索.

但这不是唯一的考虑因素.对排序列表进行二进制搜索可以提供非常快速的响应时间,而线性搜索可能需要很长时间才能生成单个项目.如果您能够在程序启动期间对列表进行排序,那么这可能是最好的方法,因为一旦程序运行,项目将被找到(或找不到)更快.对列表进行排序可以提供更好的响应时间.在启动期间支付分拣的价格比在操作期间经历非常不可预测的响应时间更好.或者发现你需要进行比你想象的更多的搜索...

Answer 2

如果您必须进行一次搜索，请进行线性搜索。这显然比排序然后二分搜索要好。
但是，如果您有多个搜索查询，则在大多数情况下，您应该首先对数组进行排序，然后对每个查询应用二分搜索。
为什么 ？假设您要执行O(k) 次搜索查询。如果您进行线性搜索，您将得到O(n*k) 次操作。如果您首先排序，则需要O(nlogn) + O(klogn) = O((n+k)logn) 次操作。什么是更好的 ？当 k 非常小时（小于 logn），最好进行线性搜索。但是，在大多数情况下，您最好先排序。