我正在学习算法并且对它们在某些情况下的应用有疑问。有分治归并排序和二分查找。两者都比线性增长算法快。
假设我想在大量数据中搜索某个值。我不知道数据是否已排序。为什么不先进行归并排序，然后再进行二分查找，而不是进行线性搜索呢？那会更快吗？或者应用归并排序然后组合二分搜索的过程会比线性搜索更慢吗？为什么？这取决于数据的大小吗？
最佳答案
您的问题前提存在缺陷。合并排序的复杂度为 O(N logN)，这是所有基于比较的排序算法中最好的，但它仍然比单个线性扫描慢很多。请注意，log2(1000) ~= 10。(显然，常数因子很重要很多，尤其是对于较小的问题规模。数组的线性搜索是其中之一CPU 可以做的最有效的事情。为 MergeSort 复制东西并不坏，因为加载和存储来自顺序地址(因此缓存和预取是有效的)，但它仍然比通过数组读取 10 次要多做很多工作.)
如果您需要支持插入/删除和查询操作的混合，所有操作都具有良好的时间复杂度，请为任务选择正确的数据结构。二叉搜索树可能是合适的(或红黑树或其他一些进行某种重新平衡以防止 O(n) 最坏情况行为的变体)。这将为您提供 O(log n) 查询和 O(log n) 插入/删除。
排序数组为您提供 O(n) 插入/删除(因为您必须将剩余元素混洗以制造或关闭间隙)，但 O(log n) 查询(时间和空间开销低于树)。
未排序数组:O(n) 查询(线性搜索)，O(1) 插入(追加到末尾)，O(n) 删除(O(n) 查询，然后随机排列元素以缩小差距).高效删除接近末尾的元素。
链表，排序或未排序:除了简单之外没有其他优点。
哈希表:插入/删除:O(1) 平均(摊销)。查询存在/不存在:O(1)。查询非现值介于哪个元素之间:O(n) 线性扫描跟踪大于 x 的最小元素和小于 x 的最大元素。
如果您的插入/删除发生在大块中，那么对新批处理进行排序并进行合并排序比一次将一个元素添加到已排序的数组更有效。 (即插入排序)。在末尾添加一个 block 并执行快速排序也是一种选择，并且可能修改更少的内存。
因此，最佳选择取决于您要优化的访问模式。
关于algorithm - 为了更快速地搜索，难道不应该在进行二分搜索之前对数据应用合并排序，还是直接跳到线性搜索？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33394321/