Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de ordenamiento»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 66:
=== Análisis ===
En el mejor de los casos, en cada paso se dividirá la secuencia en dos partes, de manera que la profundidad del árbol de llamadas iterativas será <math>\log_2n </math>, y como la cantidad de elementos a ser recorridos en cada nivel del árbol es <math>n</math>, el orden de la complejidad del algoritmo será <math>\Omega (n \log n)</math>.
En el peor caso, en cada paso se produce una partición completamente desbalanceada, es decir, queda un solo elemento de un lado, y el resto del otro lado,
* En el paso número <math>i</math> * Esto requerirá <math>n!</math> iteraciones: el orden de la complejidad del algoritmo será <math>O (n^2)</math>. Como para una distribución uniforme de los datos, el caso se asemejará mucho más al primero, se dice que el orden de la complejidad promedio del algoritmo es <math>\Theta (n \log n)</math>.
| |||