Big O of Hash Table contra Binary Search Tree

Question

¿Qué llevaría más tiempo?

imprime todos los elementos almacenados en un árbol de búsqueda binaria en orden ordenado o imprime todos los elementos almacenados en una tabla hash en orden ordenado.

Tomaría más tiempo para imprimir los elementos de una tabla hash en orden ordenado porque una tabla hash nunca se ordenó correctamente? y un BST es?

Answer 1

Estás en la correcta. Las tablas hash están ordenadas por alguna función hash, no por su orden natural, por lo que tendrías que extraer todas las entradas O (N) y ordenarlas O (NlogN) mientras que puedes recorrer un árbol de búsqueda binario en orden natural en O (NORTE).

Sin embargo, tenga en cuenta que en Java, por ejemplo, hay un LinkedHashSet y LinkedHashMap que le ofrece algunas de las ventajas de Hash pero que se pueden recorrer en el orden en que se agregaron, para poder ordenarlas y poder recorrerlo en ese orden ordenado, así como extraer elementos mediante hash.

Answer 2

Correcto, una tabla hash no está "ordenada" de la manera que probablemente desee. Por lo general, los elementos de las tablas hash no están completamente ordenados, aunque la disposición suele ser similar a la de un vecindario. Pero están dispuestos de acuerdo con la función hash, que generalmente es muy diferente para frases similares. No es un género por ninguna métrica que un humano usaría.

Si lo principal que está haciendo con su colección es imprimirlo en orden, lo mejor es usar algún tipo de BST.

Answer 3

Un árbol de búsqueda binaria se almacena de manera que si realiza un primer recorrido en profundidad, encontrará los elementos en orden ordenado (suponiendo que tenga una función de comparación consistente). La Gran O de simplemente devolver objetos que ya están en el árbol sería la Gran O de atravesar el árbol.

Tiene razón sobre las tablas hash, no están ordenadas. De hecho, para enumerar todo en una tabla hash simple, debe verificar cada segmento para ver qué hay allí, extraerlo y luego ordenar lo que obtiene. Mucho trabajo para obtener una lista ordenada de eso.

Answer 4

Corregir, imprimir los datos clasificados almacenados en una tabla hash sería más lento porque una tabla hash no está ordenada de datos. Simplemente te da una forma rápida de encontrar un artículo en particular. En "Big O Notation" se dice que el artículo se puede encontrar en tiempo constante, es decir, O (1) tiempo.

Por otro lado, puede encontrar un elemento en un árbol de búsqueda binaria en "tiempo logarítmico" (O (log n)) porque los datos ya han sido ordenados por usted.

Así que si su objetivo es imprimir una lista ordenada, es mucho mejor que los datos se almacenen en un orden ordenado (es decir, un árbol binario).

Enjoy,

Robert C. Cartaino

Answer 5

Esto nos lleva a un par de preguntas interesantes. Es un árbol de búsqueda aún más rápido teniendo en cuenta lo siguiente?

1. ¿Incorporando el tiempo de configuración tanto para Hash Table como para BST?
2. Si el algoritmo hash produce una lista ordenada de palabras. Técnicamente, podrías crear una tabla hash que use un algoritmo que sí lo haga. En ese caso, la velocidad de la BST frente a la tabla hash tendría que reducirse a la cantidad de tiempo que lleva rellenar la tabla hash en el orden ordenado.

Answer 6

También puedes ver las consideraciones relacionadas de Lista Saltar vs. Árbol Binario: Skip List vs. Binary Tree