这是G. Michael Scneider 和 Judith L. Gersting的教科书Invitation to Computer Science的直接引述。
在第 3.4.2 节的末尾，我们讨论了在未排序列表上使用顺序搜索与排序列表然后使用二分搜索之间的权衡。如果列表大小为 n=100,000，则在第二个备选方案在比较次数方面更好之前，必须进行多少次最坏情况搜索？
我真的不明白这个问题在问什么。
顺序搜索是有序的（n），二进制是有序的（lgn），在任何情况下lgn总是小于n。在这种情况下，n 已经给出，所以我应该找到什么。
这是我的家庭作业之一，但我真的不知道该怎么做。谁能用简单的英语为我解释这个问题？
并且二进制是有序的（lgn），无论如何lgn总是小于n
这是你错的地方。在作业中，您也被要求考虑排序数组的成本。
显然，如果您只需要一次搜索，第一种方法比排序数组和进行二进制搜索更好：n < n*logn + logn. 并且您被问到，您需要多少次搜索才能使第二种方法变得更有效。
提示结束。
问题是如何决定选择哪种方法 - 仅使用线性搜索或排序然后使用二进制搜索。
如果你只搜索几次线性搜索会更好——它是 O(n)，而排序已经是 O(n*logn)。如果您经常在同一个集合上搜索，排序会更好 - 多次搜索可能会变成 O(n*n) 但排序然后使用二分搜索再次搜索 O(n*logn) + NumberOfSearches*O(logn) 可以是根据 NumberOfSearches 和 n 的关系，少于或多于使用线性搜索。
任务是确定 NumberOfSearches 的确切值（不是确切的数字，而是 n 的函数），这将使选项之一更可取：
NumberOfSearches * O(n) <> O(n*logn) + NumberOfSearches * O(logn)
不要忘记每个 O() 可以有不同的常数值。
方法的顺序在这里并不重要。它告诉你当问题变得越来越大时，算法的扩展性如何。O(n)如果您只知道== 它的复杂性随着问题的大小线性增长，那么您将无法进行任何精确的计算。它不会给你任何数字。
这很可能意味着对于某些 n，具有O(n)复杂性的算法比算法更快。O(logn)因为当 O(log(n)) 变大时，它的扩展性更好，我们肯定知道，存在一个n（问题大小），具有 O(logn) 复杂度的算法更快。我们只是不知道什么时候（为了什么n）。
用简单的英语：
如果您想知道“搜索次数”，您需要精确的方程来求解，您需要精确的数字。搜索顺序需要多少次比较？（记住 n 是给定的，所以你可以给出一个数字。）使用二分搜索进行搜索需要多少次比较（在最坏的情况下！）？在进行二分搜索之前，您必须进行排序。让我们将排序所需的比较次数添加到二进制搜索的成本中。现在比较这两个数字，哪个少？
二进制搜索很快，但排序很慢。顺序搜索比二分搜索慢，但比排序快。然而，排序只需要进行一次，无论您搜索多少次。那么，一个繁重的排序何时比每次都进行缓慢（顺序）搜索更重要？
祝你好运！
对于顺序搜索，最坏的情况是 n = 100000，因此对于 p 个搜索，需要 p × 100000 次比较。
使用 Θ(n2) 排序算法将需要 100000 × 100000 次比较。
二进制搜索需要 1 + log n = 1 + log 100000 = 每次搜索的 17 次比较，
总共会有 100000×100000 + 17p 的比较。
第一个表达式大于第二个，表示 100000p > 100000^2 + 17p
对于 p > 100017。
感谢你们。我想我现在明白了。你能看看我的答案，看看我是否走在正确的轨道上。
对于最坏情况搜索，顺序搜索的比较次数为 n = 100,000。二分查找的比较次数为 lg(n) = 17。排序的比较次数为 (n-1)/2 * n = (99999)(50000)。（我正在按照我的教科书并使用我课堂上的选择排序算法）
所以设 p 是最坏情况搜索的次数，然后 100,000p > (99999)(50000) + 17p
OR p > 50008
总之，我需要 50,008 次最坏情况搜索来进行排序和使用二分搜索，而不是顺序搜索 n=100,000 的列表。
问题是要了解NUM_SEARCHES补偿分拣成本所需的数量。所以我们会有：
time( NUM_SEARCHES * O(n) ) > time( NUM_SEARCHES * O(log(n)) + O(n* log(n)) )