Una ordenación basada en la comparación puede ordenar en tiempo lineal en algunos casos; por ejemplo, considere la clasificación de inserción en una matriz ya ordenada. Sin embargo, todos los tipos basados en la comparación en el peor de los casos se ejecutarán en al menos n log n time.
Prueba: todos los géneros basados en la comparación se pueden representar mediante un árbol de decisión (binario), en el que cada nodo representa una comparación, una rama corresponde a un resultado de la comparación y las hojas son la salida del género. La profundidad del árbol, o la longitud del camino simple más largo a una hoja del árbol, es igual al número de comparaciones realizadas en el peor de los casos.
Un árbol de decisión para una ordenación correcta basada en la comparación debe tener al menos n! hojas, ya que hay n! Las permutaciones de n números y cualquier permutación individual podrían ser la salida correcta del tipo. El número máximo de hojas para un árbol binario completo de profundidad d es 2 ^ d .
- ¿Cuándo es conveniente resolver un problema usando un algoritmo codicioso?
- ¿Por qué la programación dinámica se llama programación dinámica?
- En este algoritmo de clasificación de radix, ¿qué representa cada variable? (Java)
- Cómo ordenar matrices en C
- ¿Cuál es la última actualización del algoritmo SEO de Google en 2017?
Por lo tanto, ¡el número de hojas de un árbol de decisión de profundidad d debe ser mayor o igual que n! y menor o igual que 2 ^ d . Tome el log base 2 de las expresiones, lo que resulta en d es mayor o igual que log (n!) . Log (n!) Es Omega ( n log n ), entonces d , o la profundidad del árbol, también es Omega ( n log n ).
Entonces, el peor tiempo de ejecución para cualquier ordenamiento basado en comparación tiene un límite inferior de n log n .
