Was würde länger dauern?Großes O der Hashtabelle vs. Binärsuchbaum
Alle in einer binären Suchstruktur gespeicherten Elemente in sortierter Reihenfolge drucken oder alle in einer Hash-Tabelle gespeicherten Elemente in sortierter Reihenfolge drucken.
Es würde länger dauern, die Elemente einer Hash-Tabelle in sortierter Reihenfolge zu drucken, weil eine Hash-Tabelle nie richtig sortiert ist? und ein BST ist?
Sie haben Recht. Hashtabellen werden nach einer Hashfunktion sortiert, nicht nach ihrer natürlichen Sortierreihenfolge. Sie müssen also alle Einträge O (N) extrahieren und sie O (NlogN) sortieren, während Sie einen binären Suchbaum in natürlicher Reihenfolge in O durchlaufen können (N).
Beachten Sie jedoch, dass es in Java zum Beispiel ein LinkedHashSet und LinkedHashMap gibt, die Ihnen einige der Vorteile von Hash bieten, die aber in der Reihenfolge durchlaufen werden können, in der sie hinzugefügt wurden, so dass Sie sie sortieren und können traversiere es in dieser sortierten Reihenfolge und extrahiere Elemente durch Hash.
Richtig, eine Hash-Tabelle wird nicht so "sortiert", wie Sie es wahrscheinlich wollen. Elemente in Hash-Tabellen sind normalerweise nicht vollständig sortiert, obwohl die Anordnung oft in der Nähe einer Sorte liegt. Aber sie sind nach der Hash-Funktion angeordnet, die für ähnliche Sätze normalerweise sehr unterschiedlich ist. Es ist keine Art von Metrik, die ein Mensch benutzen würde.
Wenn Sie hauptsächlich mit Ihrer Sammlung in sortierter Reihenfolge drucken, verwenden Sie am besten eine Art von BST.
Ein binärer Suchbaum wird so gespeichert, dass Sie die Elemente in einer sortierten Reihenfolge finden (vorausgesetzt, Sie haben eine konsistente Vergleichsfunktion). Das große O des einfachen Zurückgebens von Gegenständen, die bereits in dem Baum sind, würde das Große O sein, das den Baum durchquert.
Sie haben korrekte Hash-Tabellen, sie sind nicht sortiert. In der Tat, um alles in einer einfachen Hash-Tabelle aufzählen zu können, müssen Sie jeden Bucket überprüfen, um zu sehen, was drin ist, herausziehen und dann sortieren, was Sie bekommen. Viel Arbeit, um eine sortierte Liste daraus zu machen.
Korrekt, Drucken sortierte Daten in einer Hash-Tabelle gespeichert würde langsamer sein, weil eine Hash-Tabelle Daten nicht sortiert ist. Es gibt Ihnen nur eine schnelle Möglichkeit, einen bestimmten Artikel zu finden. In "Big O Notation" wird gesagt, dass der Gegenstand in konstanter Zeit, d. H. O (1), gefunden werden kann.
Auf der anderen Seite können Sie ein Element in einem binären Suchbaum in "logarithmischer Zeit" (O (log n)) finden, da die Daten bereits für Sie sortiert wurden.
Also, wenn Sie Ziel ist es, eine sortierte Liste zu drucken, sind Sie viel besser dran, um die Daten in einer sortierten Reihenfolge gespeichert (d ein binärer Baum).
Genießen,
Robert C. Cartaino
Das bringt ein paar interessante Fragen auf. Ist ein Suchbaum in Anbetracht des Folgenden noch schneller?
Überprüfen Sie auch ähnliche Überlegungen überspringen Liste vs. Binary Tree: Skip List vs. Binary Tree