Finden Sie maximale Element in Hash-Tabelle mit doppelt verketteten Liste in jedem Steckplatz

Question

Es gibt eine Hash-Tabelle, Steckplätze in einem Array, jeder Steckplatz hat eine doppelt verknüpfte Liste, unsortiert.

Die Gesamtzahl der Elemente ist n, die Anzahl der Steckplätze ist m.

Was ist die Zeit, die Komplexität zu:

• Finden Sie das maximale Element in ganz hashtable.
• Finden Sie das Nachfolgerelement für ein gegebenes Element x.

Sie sollten beide O(n), richtig sein? Weil Sie jedes Element durchlaufen müssen.

Aber in dem Buch <The algorithm design manual 2nd>, Seite 90, sagt es, es ist O(n+m), aber ich verstehe es nicht.

Jeder, helfen zu sagen, was richtig ist? Und warum.

Danke.

Answer 1

Steckplätze können leer sein (keine Elemente in der Liste enthalten). Sie müssen alle Slots durchlaufen, um alle nicht leeren Listen zu finden, also ist O (m) funktioniert. Dann musst du alle Listen durchsuchen, was O (n) funktioniert. Gesamtarbeit: O (n + m).