<分区>
假设我们想在数组中找到一些已知的键并提取值。有两种可能的方法(也许更多？)来做到这一点。线性方法，在此期间我们将比较每个数组键与针 O(N)。或者我们可以对这个数组 O(N*log(N)) 进行排序并应用二进制搜索 O(log(N))。我对此有几个问题。
因此，正如我所见，排序与搜索密切相关，但独立的排序是无用的。排序是一种简化搜索的工具。我对么？或者还有其他排序的实现方式吗？
如果我们要谈论搜索，那么我们可以搜索未排序的数据 O(N) 和排序的 O(N*log(N)) + O(log(N) )。搜索可以与排序分开存在。如果我们只需要在数组中查找一次我们应该使用线性搜索，如果重复搜索我们应该对数据进行排序并在它之后执行搜索？
最佳答案
不要认为在每次搜索之前都需要 O(n * lg(n)) 排序。这将是荒谬的，因为 O(n * lg(n)) + O(log(n)) > O(n) 对随机顺序数据进行线性搜索会更快平均为 O(n/2)。
想法是最初使用 O(n * lg(n)) 算法对随机数据进行一次排序，然后在排序之前添加的任何数据都应按顺序添加，以便之后的每次搜索可以在 O(lg(n)) 时间内完成。
您可能会对查看 hash tables 感兴趣这是一种未排序但具有 O(1) 恒定访问时间的数组。
关于algorithm - 排序和搜索关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20432146/