链式哈希表的时间复杂度是多少?

Question

我有一个哈希表，它由1000个元素和100个桶组成，每个桶最多有100个条目。假设一个bucket有100个条目(即该bucket的列表中有100个条目)。现在用大0符号表示的时间复杂度是多少如果我要找的东西是桶列表中的第100个。O(100)还是O(n)?还有别的吗?

Answer 1

大0表示法的要点是，您不"假设一个桶有100个条目"，您让它的条目数为n，并得到一个以n为单位的表达式。

对于列表中的n项，时间复杂度将为O(n)，忽略您使用的任何散列函数。

注意，这是最坏的情况(最后一项)，平均而言，搜索在O(1)中运行。

Answer 2

你的问题没有意义，因为大o符号表达了效率如何随着元素数量的变化而变化，例如元素数量增加超过1000，而你没有告诉我们这种行为。

例如，查找特定元素的大o符号效率可能是:

• 如果元素位于桶尾的元素永远不会超过100个，那么O(1)

• 如果元素停留在桶的位置100，那么即使在它之后追加了更多的项，假设搜索将从桶的开始开始，那么它仍然是0 (1)

• 如果该bucket中的元素个数保持在N/10，并且你不能指望该特定元素在bucket的列表中保持固定位置，那么它是O(N)

• 如果元素停留在bucket的末尾，但其中的元素个数总是N的立方根的平方，那么O(平方(立方根(N)))

• 如果元素停留在bucket的末尾，并且其中的元素数量总是在3 * sqrt(N)左右，则0 (sqrt(N))

可以看到，O表示搜索时间与元素总数的关系，但是您没有给出足够的数据点来描述曲线。