¿Quicksort siempre tiene tiempo de ejecución cuadrático si elige un elemento máximo como pivote?

9

Si tiene un algoritmo de clasificación rápida y siempre selecciona el elemento más pequeño (o más grande) como pivote; ¿estoy en lo cierto al suponer que si proporciona un conjunto de datos ya ordenados, siempre obtendrá el peor rendimiento independientemente de si su lista 'ya ordenada' está en orden ascendente o descendente?

Mi opinión es que, si siempre elige el elemento más pequeño para su pivote, entonces si su entrada 'ya ordenada' está ordenada en forma ascendente o descendente no importa porque el subconjunto elegido para ser ordenado en relación con su pivote siempre será el ¿mismo tamaño?

algorithms time-complexity algorithm-analysis runtime-analysis sorting yoonsi
fuente

2

Su pensamiento es correcto, pero también puede discutir directamente y calcular el tiempo de ejecución de la clasificación rápida en este caso: obtendrá .

O (n^{2})

$O(n^2)$

Yuval Filmus

15

La peor complejidad de caso para quicksort es . Esto se logra seleccionando pivotes que dividen el conjunto de modo que un grupo tenga un solo miembro. Con un algoritmo de selección de pivote incorrecto, esto se puede lograr fácilmente eligiendo un extremo de un conjunto ordenado. Tu suposición es correcta. $\Theta(n^2)$

walrii
fuente

2

Era mejor escribirlo: "... Esto se logra seleccionando pivotes que dividen el conjunto de modo que un grupo solo tenga un miembro O (1)"

@Saeed Amiri: Eso es correcto, pero es mejor ser preciso.

MMS

1

@SaeedAmiri: O (1) indica que es proporcional a 1, lo que significa que puede ser k * 1. El peor de los casos reales se logra cuando es exactamente 1. Te concederé que O (1) todavía puede conducir a O (n ^ 2).

walrii

@MMS, escribí para ser precisos, walrii Escribiste: "La peor complejidad de caso para quicksort es ..", pero de hecho, la única forma de lograr no es la forma en que dijiste, sí, la forma en que lo describiste es el peor de los casos, pero no el único .

O (1)

$O(1)$

Θ (n^{2})

$\Theta (n^2)$

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta (n^2)$

5

¡Si! ¡Estás pensando que tiene toda la razón! Y como lo mencionó correctamente Yuval Filmus, el tiempo de ejecución será $\Theta(n^2)$

n0nChun
fuente

3

Una submatriz tendrá o elemento, mientras que la otra tendrá elementos ; por lo tanto, es : $0$ $1$ $(n-1)$ $O(n^2)$

t (n) = t (n - 1) + t (0) + O (n) = O (n^{2})

$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$

sulava
fuente

¿Quicksort siempre tiene tiempo de ejecución cuadrático si elige un elemento máximo como pivote?

Respuestas: