Big O de Hash Table vs. binaire Recherche Arbre

Question

Ce qui prendrait plus de temps?

imprimer tous les éléments stockés dans un arbre de recherche binaire dans l'ordre de tri ou d'imprimer tous les éléments stockés dans une table de hachage dans l'ordre.

Il faudrait plus d'imprimer les éléments d'une table de hachage dans l'ordre de tri, car une table de hachage est jamais triée correcte? et un BST est?

Answer 1

Vous avez raison. Hashtables sont triés par une fonction de hachage, non pas par leur ordre de tri naturel, de sorte que vous auriez à extraire toutes les entrées O (N) et les trier O (NlogN) alors que vous pouvez parcourir un arbre de recherche binaire dans l'ordre naturel dans O ( N).

Notez cependant que Java, par exemple, il y a un LinkedHashSet et LinkedHashMap qui vous donne quelques-uns des avantages de Hash, mais qui peut être déplacé dans l'ordre qu'il a été ajouté à, pour que vous puissiez trier et être en mesure de traverser dans l'ordre que tri ainsi que l'extraction des éléments par hachage.

Answer 2

Corriger, une table de hachage n'est pas « sorted » de la manière que vous voulez probablement. Les éléments de tables de hachage ne sont pas tout à fait complètement triés, en général, bien que l'arrangement est souvent un peu dans le quartier d'une sorte. Mais ils sont disposés en fonction de la fonction de hachage, qui est généralement très différentes des expressions similaires. Ce n'est pas une sorte par une mesure utiliserait un être humain.

Si la principale chose que vous faites avec votre collection est-il l'impression dans l'ordre de tri, vous êtes mieux en utilisant un certain type de BST.

Answer 3

Un arbre de recherche binaire est stocké d'une manière que si vous faites une profondeur d'abord traversal, vous trouverez les articles dans l'ordre de tri (en supposant que vous avez une fonction cohérente de comparaison). Le Big O de simplement le retour d'articles déjà dans l'arbre serait le Big O de traverser l'arbre.

Vous avez raison sur les tables de hachage, ils ne sont pas triés. En fait, afin d'énumérer tout dans une table de hachage ordinaire, vous devez vérifier chaque seau pour voir ce qui est là-dedans, tirez, puis trier ce que vous obtenez. Beaucoup de travail pour obtenir une liste triée sur ce sujet.

Answer 4

Corriger, les données triées d'impression stockées dans une table de hachage serait plus lente, car une table de hachage ne sont pas triées données. Il vous donne juste un moyen rapide de trouver un élément particulier. Dans « Big O Notation » il est dit que l'élément se trouve dans le temps constant, à savoir O (1) heure.

Par contre, vous pouvez trouver un élément dans un arbre de recherche binaire en « temps logarithmique » (O (log n)), car les données ont déjà été triés pour vous.

Donc, si votre objectif est d'imprimer une liste triée, vous êtes beaucoup mieux d'avoir les données stockées dans un ordre (à savoir un Sorted arbre binaire).

Profitez,

Robert C. Cartaino

Answer 5

Cela soulève quelques questions intéressantes. Est-ce un arbre de recherche encore plus rapide considérant ce qui suit?

1. L'intégration du temps de configuration à la fois la table de hachage et de la BST?
2. Si l'algorithme de hachage produit une liste triée des mots. Techniquement, vous pouvez créer une table de hachage qui utilise un algorithme qui fait. Dans ce cas, la vitesse du BST vs la table de Hash devrait descendre à la quantité de temps qu'il faut pour remplir la table de hachage dans l'ordre de tri.

Answer 6

Consultez également les considérations connexes de Skip Liste vs. Binary Tree: Liste Ignorer vs Binary Tree