在每个槽中使用双向链表查找哈希表中的最大元素

Question

有一个哈希表,一个数组中的槽,每个槽都有一个双向链表,未排序.

总元素数是n,插槽数是m.

什么是时间复杂度:

• 在整个哈希表中查找最大元素.
• 找到给定元素x的后继元素.

他们应该是两个O(n),对吗？因为你必须迭代每个元素.

但是,在第90页的书中<The algorithm design manual 2nd>,它说它是,但我没有得到它.O(n+m)

任何人,帮忙告诉哪个是对的？而且,为什么.

谢谢.

Answer 1

插槽可以为空(列表中没有元素).您必须迭代所有插槽才能找到所有非空列表,这样O(m)才能正常工作.然后你必须搜索所有列表,这是O(n)工作.总工作量:O(n + m).