Usando árbol rojo-negro para la clasificación

Question

El peor de los casos el tiempo de funcionamiento de la inserción en un red-black tree es O(lg n) y si realizo una in-order walk en el árbol, que esencialmente visitar cada nodo, por lo que el total del peor de los casos el tiempo de ejecución para imprimir la colección ordenada sería O (n lg n)

Tengo curiosidad, ¿por qué se red-black trees no se prefiere para la clasificación sobre quick sort (cuyo promedio de los casos el tiempo de funcionamiento es O(n lg n).

veo que tal vez porque no lo hacen red-black trees tipo in- colocar, pero no estoy seguro, así que tal vez alguien podría ayudar.

Answer 1

Saber qué algoritmo de ordenación tiene un mejor rendimiento realmente dependerá de sus datos y situación.

Si estamos hablando en términos generales/prácticas,

ordenación rápida (aquel en el que se selecciona al azar el pivote/Sólo tiene que elegir uno fijo, lo peor de los casos Omega (n^2)) podría ser mejor que Rojo- Árboles negros porque (no necesariamente en orden de importancia)

• Quicksort está en su lugar. El mantiene su huella de memoria baja. Digamos que esta rutina de quicksort fue parte de un programa que trata con una gran cantidad de datos. Si mantuvo el uso de grandes cantidades de memoria, su sistema operativo podría comenzar a intercambiar la memoria de su proceso y dañar su desempeño.

• Los accesos a la memoria del Quicksort están localizados. Esto funciona bien con el almacenamiento en caché/intercambio.

• Quicksort se puede paralelizar fácilmente (probablemente más relevante actualmente).

• Si tratara de optimizar la ordenación binaria de árboles (utilizando un árbol binario sin equilibrar) mediante el uso de una matriz, ¡terminará haciendo algo así como Quicksort!

• Los árboles rojo-negro tienen gastos generales de memoria. Tiene que asignar nodos posiblemente varias veces, sus requisitos de memoria con árboles es el doble/triple que el uso de matrices.

• Después de ordenar, digamos que quería el elemento 1045º (por ejemplo), tendrá que mantener las estadísticas de orden en su árbol (costo de memoria adicional debido a esto) y tendrá el tiempo de acceso O (logn)!

árboles

• rojo-negro tienen los gastos generales sólo para acceder al siguiente elemento (búsquedas de puntero)

árboles

• rojo-negro no juegan bien con el caché y los accesos puntero podrían inducir más intercambio.

• La rotación en árboles rojo-negro aumentará el factor constante en el O (nlogn).

• Quizás la razón más importante (pero no válida si tiene disponible lib, etc.), Quicksort es muy simple de comprender e implementar. ¡Incluso un niño de escuela puede entenderlo!

¡Diría que intentas medir ambas implementaciones y ver qué pasa!

Además, Bob Sedgewick hizo una tesis en el quicksort! Puede valer la pena leer.

Answer 2

Hay un montón de algoritmos de clasificación que son el peor caso O(n log n) - por ejemplo, tipo de fusión. La razón por la que se prefiere el método rápido es porque es más rápido en la práctica, aunque algorítmicamente puede no ser tan bueno como otros algoritmos.

A menudo, los géneros incorporados utilizan una combinación de varios métodos según los valores de n.

Answer 3

Las medidas de complejidad de Big-O no suelen tener en cuenta los factores escalares, por ejemplo, O (2n) y O (4n) suelen reducirse a O (n). El análisis de complejidad de tiempo se basa en pasos operativos a un nivel algorítmico, no a un nivel de programación estricto, es decir, sin código fuente o consideraciones de instrucción de máquina nativa. Quicksort es generalmente más rápido que la ordenación basada en árboles ya que (1) los métodos tienen la misma complejidad de tiempo promedio algorítmica y (2) las operaciones de búsqueda e intercambio requieren menos comandos de programa y acceso a datos -árboles negros, incluso si el árbol utiliza una implementación subyacente basada en arreglos. El mantenimiento de las restricciones del árbol rojo-negro requiere pasos operacionales adicionales, almacenamiento/acceso al valor del campo de datos (colores del nodo), etc., que los simples pasos de intercambio de partición de matriz de un quicksort.

El resultado neto es que los árboles rojo-negro tienen coeficientes escalares más altos que los del quicksort que están siendo oscurecidos por el resultado del análisis de complejidad de tiempo promedio O (n log n).

Algunas otras consideraciones prácticas relacionadas con arquitecturas de máquina se discuten brevemente en la Quicksort article on Wikipedia

Answer 4

En general, las representaciones de los algoritmos O (nlgn) se pueden ampliar a A * nlgn + B, donde A y B son constantes. Hay muchas pruebas algorítmicas que muestran que los coeficientes para quicksort son más pequeños que los de otros algoritmos. Eso está en el mejor de los casos (la clasificación rápida funciona de forma horrible en los datos clasificados).

Answer 5

Hola, la mejor manera de explicar la diferencia entre todas las rutinas de clasificación en mi opinión es. (Mi respuesta es para las personas que están confundidas acerca de qué tan rápido el ordenamiento es más rápido en la práctica que otro algoritmo de clasificación).

"Creo que se está ejecutando en una computadora muy lenta".

1. Lo primero es que una operación de comparación demora 1 hora.
2. Una operación de cambio demora 2 horas.

"Estoy usando la hora solo para que la gente entienda lo importante que es el tiempo".

Ahora, de todas las operaciones de clasificación de ordenación rápida, tienen muy pocas comparaciones y muy menos intercambio de elementos.

Quick-sort es más rápido por esta razón principal.

Answer 6

Hay muchos casos en que los árboles de red-back no son malos para la clasificación. Mi pruebas mostraron, en comparación con el tipo de combinación natural, que los árboles rojo-negro sobresalen donde:

Los árboles son mejores para Dups: Todas las pruebas en las que dups necesitan ser eleminated, algoritmo de árbol es mejor.Esto no es sorprendente, ya que el árbol puede mantenerse muy pequeño desde el principio, por lo que los algoritmos que están diseñados para el ordenamiento de arreglos en línea podrían pasar alrededor de segmentos más grandes durante más tiempo.

Árboles son mejores para Aleatorio: Todas las pruebas con algoritmo de árbol aleatorio son mejores. Esto tampoco es sorprendente, ya que en un árbol la distancia entre los elementos es más corta y el desplazamiento no es necesario. Por lo tanto, insertarlo repetidamente en un árbol podría requerir menos esfuerzo que ordenar una matriz.

Así que tenemos la impresión de que el tipo de fusión natural solo se destaca en casos especiales ascendentes y descendentes. Que ni siquiera se puede decir para ordenar rápidamente.

Gist con los casos de prueba here.

P.S .: se debe tener en cuenta que el uso de árboles para la clasificación no es trivial. Uno no solo debe proporcionar una rutina de inserción, sino también una rutina que puede linealizar el árbol a una matriz. Actualmente estamos utilizando una rutina get_last y una predecesora, que no necesita una pila. Pero estas rutinas no son O (1) ya que contienen bucles.