* Mejor caso: O (n log n)
* Caso promedio: O (n log n)
* peor de los casos: O (n^2)
Aquí hay un desglose:
* El mejor caso y el caso promedio (o (n log n)): Esto ocurre cuando el elemento pivote elegido en cada paso divide la matriz en mitades aproximadamente iguales. En este escenario, el algoritmo hace llamadas recursivas log n (porque está a la mitad de manera efectiva del tamaño del problema), y cada nivel de recursión requiere que O (n) funcione para dividir la matriz. Por lo tanto, la complejidad del tiempo general es O (n log n).
* peor de los casos (o (n^2)): Esto sucede cuando el elemento pivote es repetidamente el elemento más pequeño o más grande de la matriz. Esto lleva a particiones muy desiguales. En esencia, en lugar de dividir la matriz por la mitad, solo está reduciendo el tamaño del problema en un elemento cada vez. Esto da como resultado que N llamadas recursivas, y cada llamada todavía lleva O (n) tiempo a particionar (porque está comparando casi todos los elementos). En consecuencia, la complejidad del tiempo general se degrada a O (N^2).
Mitigación del peor de los casos:
El peor de los casos puede ser mitigado por:
* Selección de pivote aleatorizado: Elegir el pivote al azar ayuda a evitar elegir consistentemente el elemento más pequeño o más grande, lo que hace que el caso O (n^2) sea mucho menos probable.
* Selección de pivote mediana de tres: Seleccionar la mediana de la primera, media y última parte de la matriz como pivote también puede ayudar a evitar elecciones de pivote consistentemente malas.
En la práctica, Quicksort a menudo es muy eficiente debido a su buen rendimiento promedio y al hecho de que tiende a tener factores constantes más bajos que otros algoritmos de clasificación O (N log n) como el tipo de fusión. Sin embargo, es importante ser consciente del potencial para el comportamiento O (n^2) en el peor de los casos.