假设有一个包含未排序数据的数组，我需要选择线性搜索或二进制搜索进行搜索。那我应该选择哪个选项？线性搜索的时间复杂度为 O(n)，二分搜索的时间复杂度为 O(log n)。但是，最快的排序算法给出了 O(n * log n) 的时间复杂度。现在，我不知道如何“添加”两种算法的复杂性（如果这是正确的话），因此，我在问这个问题。
所以我的问题是，如果排序然后二进制搜索比简单的线性搜索更好，还是相反？
另外，我如何证明可能使用大 O 表示法的任何情况（我的意思是“添加”和“比较”时间复杂度）？
非常感谢您的阅读！！！那意义重大。
你并没有真正“增加”复杂性。正如您所说，排序是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)，您将使用顺序搜索。否则使用排序然后二进制搜索。
但这不是唯一的考虑因素。对已排序列表进行二分搜索可提供非常快的响应时间，而线性搜索对于单个项目可能需要很长时间。如果您有能力在程序启动期间对列表进行排序，那么这可能是最好的方法，因为一旦程序运行，就会更快地找到（或找不到）项目。对列表进行排序可为您提供更好的响应时间。最好在启动期间付出排序的代价，而不是在操作期间经历非常不可预测的响应时间。或者发现您需要进行比您想象的更多的搜索。. .
如果您必须进行一次搜索，请进行线性搜索。这显然比排序然后二进制搜索要好。
但是，如果您有多个搜索查询，在大多数情况下，您应该首先对数组进行排序，然后对每个查询应用二进制搜索。
为什么 ？假设您要执行O(k)搜索查询。如果您进行线性搜索，您将得到O(n*k)操作。如果你首先排序，那将需要O(nlogn) + O(klogn) = O((n+k)logn)操作。什么是更好的 ？当 k 非常小（小于 logn）时，最好进行线性搜索。但是在大多数情况下，您最好先进行排序。
所以我的问题是，如果排序然后二进制搜索比简单的线性搜索更好
是的你是对的。
当数组已经排序时，应该应用二进制搜索。否则你不能使用二分查找。如果您有大量查询，最好先对数组进行排序，然后再应用二分查找。但是，如果您只有几个查询，那么线性搜索可能就足够了。
至于大 O 表示法，它始终是“大”部分——即，如果你排序然后二进制搜索，它将是 O(n*lgn)。如果只使用线性搜索，则为 O(n)。但是当考虑到查询的数量（m）时，第一种方法将是 O(n*lgn + m*lgn)，而第二种方法是 O(m*n)。您可以看到，如果 m 很大（m=n 或 m>>n），则第二种方法将比二分查找更复杂。