Найти максимальный элемент в хеш-таблице с дважды связанным списком в каждом слоте

Question

Существует хеш-таблица, слоты в массиве, каждый слот имеет двусвязный список, unsorted.

Общее количество элементов - n, количество слотов - m.

Какова временная сложность для:

• Найти максимальный элемент в целом Hashtable.
• Найдите элемент-преемник для данного элемента x.

Они должны быть как O(n), так? Потому что вам нужно перебирать каждый элемент.

Но, в книге <The algorithm design manual 2nd>, страница 90, он говорит, что это O(n+m), но я не понимаю.

Кто-нибудь, помогите определить, что является правильным? И почему.

Спасибо.

Answer 1

Слоты могут быть пустыми (не имеют элементов в списке). Вы должны перебрать все слоты, чтобы найти все непустые списки, так что это O (m). Затем вам нужно искать все списки, которые работают O (n). Общая работа: O (n + m).