No puede haber nada mejor que una clasificación rápida para responder a esto basado en la teoría de la aleatorización.
Considere que tiene 7 números: 7 6 5 4 3 2 1
1) peor de los casos: si adoptamos una estrategia para usar constantemente el número izquierdo como pivote, la partición no ayudará mucho, ya que todo el número residiría en el lado izquierdo del pivote, haciendo que el árbol de partición esté sesgado. Resultado, un algoritmo de complejidad de tiempo O (n ^ 2).
- ¿Cuáles son los objetivos del aprendizaje de la estructura de datos?
- ¿Por qué el orden de selección no se denomina orden de intercambio?
- ¿Dejarías que los algoritmos se intercambiaran por ti cuando estés en el trabajo?
- ¿Qué es un algoritmo? ¿Es simplemente una máquina de Turing? Si no, ¿qué es?
- ¿Cuál es el punto de los algoritmos gráficos?
2) Tomando el mismo conjunto de datos, si elegimos aleatoriamente el pivote del conjunto, existe una gran posibilidad de que caiga en el rango de corchetes BUENOS SUFICIENTES (n / 4 a 3n / 4) con una altura del árbol de partición del peor de los casos como registro 4/3 n (esto es simple de probar con pivote constantemente elegido para particionar datos en tamaño 1/4 y 3/4 en el peor de los casos). Esta elección de pivote aleatorio podría dar como resultado un tiempo amortizado de O (nlogn) en general.
3) Es por esta razón que el tiempo de ejecución esperado de clasificación rápida es generalmente cercano a O (nlogn) ya que la aleatorización resulta principalmente en un equilibrio de pivotes buenos a lo suficientemente buenos a malos …
