logo标签列表

使用字典而不是排序和搜索

pythonalgorithmsortingdictionary
3
我正在研究哈希表，想到了一个问题：为什么不用字典来搜索元素，而先将列表排序再进行二分搜索呢？（假设我要多次搜索）
我们可以在O(n)时间内将列表转换为字典（我认为），因为我们必须遍历所有元素。我们将所有这些元素添加到字典中，这需要O(1)的时间。当字典准备好后，我们就可以在O(1)的时间（平均值）内搜索任何元素，最坏情况是O(n)。
如果我们谈论平均情况，O(n)比其他排序算法更好，因为它们最好需要O(nlogn)。如果我对我所说的一切正确，那么为什么不这样做呢？
我知道还有其他各种可以使用排序元素但不能在未排序的字典或数组中完成的事情。但如果我们只关注搜索，难道不是比其他排序算法更好的方法吗？
1
还是我们只需在O(n)时间内遍历未排序的列表来搜索元素？ - timgeb
1
@timgeb，如果您需要进行n次搜索，则复杂度为n*O(n)，如果您首先进行排序，然后再进行n次搜索，则为n*O(logn)。根据约翰理论，您可以在O(1)时间内进行任意次数的搜索，这比您所说的要好得多。 - user5936276
@jamessmith 是的，但你没有提到你想要多次搜索。在这种情况下，将列表转换为集合（为什么要字典？）以O(n)的时间复杂度进行操作，然后在O(1)的时间内进行任何后续包含检查。只有当您需要顺序和/或重复元素时，保持排序列表并进行二分是有帮助的。 - timgeb
@timgeb 那为什么要使用排序算法来进行搜索呢？这是一个更好的想法。 - sid597
2
我认为将列表转换为集合（作为哈希映射的特殊情况）以进行快速重复查找是一种相当普遍的做法。如果你的空间非常有限，使用排序列表可能更可取，因为稀疏填充的哈希集比原始列表占用更多的空间（哈希集越密集，发生碰撞的次数就越多）。 - tobias_k
显示剩余6条评论
2个回答
2

没错，一个设计良好的哈希表能够胜过排序和搜索。

但是要做出正确的选择，需要考虑很多因素，比如是否需要原地操作、数据集的动态性、搜索次数与插入/删除次数的比例、构建有效哈希函数的难易程度等等...

1
二分查找是一种搜索技术，它利用了已经排序的key列表这一事实，不需要对其进行排序再搜索，使得其最坏情况下的搜索时间为O(log n)。
如果您没有一个有序的key列表并且想要搜索一个key，那么您将不得不采用线性搜索，其最坏情况下将以O(n)的复杂度运行，没有必要先排序再搜索，因为已知的最好的排序算法只能在O(n log n)的时间内工作。
从一个键列表中建立字典并执行查找在这里没有优势，因为线性搜索将产生与更好的性能相同的结果，并且还需要辅助内存，这在使用字典的情况下是必需的；然而，如果您有多个查找且键空间较小，则使用字典可以带来优势，因为构建字典是一次O(n)的工作，随后的查找可以通过O(1)的代价进行，尽管会使用字典的一些内存。
2
如果你已经知道你要找的关键字，那么这就不叫搜索了。我不理解这句话。你正在寻找你事先知道的关键字的存在。你怎么可能搜索你不知道的东西呢？ - Miljen Mikic
1
“最知名的排序算法” - 实际上，数学证明了排序所需的时间不可能少于 O(n log n) + c。现今的算法都试图将常数 c 最小化。 - Amit Gold
线性搜索的最坏情况复杂度为O(n)，无需先排序再搜索，因为最好的已知排序算法只能在O(n log n)时间内工作。为什么你认为我在问题中说了这种情况呢？（假设我想要进行多次搜索） - sid597
@johnsmith 如果您在固定列表中进行多个搜索，则您的技术确实更好，而且这是常用的方法。 - anand
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接