¿Por qué el Randomized Quicksort tiene O (n log n) el peor costo de tiempo de ejecución

La ordenación rápida aleatoria es una extensión de la ordenación rápida en la que el elemento pivote se elige aleatoriamente. ¿Cuál puede ser la peor complejidad de tiempo de este algoritmo? Según yo, debería ser , ya que el peor de los casos ocurre cuando el pivote elegido al azar se selecciona en orden ordenado o en orden inverso . Pero en algunos textos [1] [2] su peor complejidad de tiempo se escribe como$O(n^2)$$O(n\log{n})$

Que es correcto

Ambas fuentes hacen referencia al "peor tiempo de ejecución esperado" de Supongo que esto se refiere al requisito de tiempo esperado, que difiere del peor de los casos.$O(n \log n).$

Quicksort generalmente tiene un requisito absoluto de tiempo en el peor de los casos de . El peor caso se produce cuando, a cada paso, el procedimiento de partición divide una n array -Longitud en matrices de tamaño 1 y n - 1 . Esta selección "desafortunada" de elementos dinámicos requiere llamadas recursivas O ( n ) , lo que lleva a un peor caso O ( n 2 ) .$O(n^2)$$n$$1$$n-1$$O(n)$$O(n^2)$

Elegir el pivote aleatoriamente o barajar aleatoriamente la matriz antes de ordenar tiene el efecto de hacer que el peor de los casos sea muy improbable, particularmente para matrices grandes. Ver Wikipedia para una prueba de que la esperada requisito de tiempo es . Según otra fuente , "la probabilidad de que quicksort use un número cuadrático de comparaciones al ordenar una gran matriz en su computadora es mucho menor que la probabilidad de que su computadora sea golpeada por un rayo".$O(n\log n)$

Editar:

Según el comentario de Bangye, puede eliminar la secuencia de selección de pivote en el peor de los casos seleccionando siempre el elemento mediano como pivote. Dado que encontrar la mediana toma tiempo, esto da Θ ( n log n ) en el peor de los casos. Sin embargo, dado que es muy poco probable que la clasificación rápida aleatorizada tropiece con el peor de los casos, rara vez se utiliza la variante determinista de búsqueda rápida de clasificación media.$O(n)$$\Theta(n \log n)$

Te faltabas que estos textos hablaran del "peor tiempo de ejecución esperado ", no del "peor tiempo de ejecución".

Están discutiendo una implementación de Quicksort que involucra un elemento aleatorio. Normalmente tiene un algoritmo determinista, que es un algoritmo que para una entrada dada siempre producirá exactamente los mismos pasos. Para determinar el "peor tiempo de ejecución", examine todas las entradas posibles y elija la que produce el peor tiempo de ejecución.

Pero aquí tenemos un factor aleatorio. Dada alguna entrada, el algoritmo no siempre realizará los mismos pasos porque hay algo de aleatoriedad involucrado. En lugar de tener un tiempo de ejecución para cada entrada fija, tenemos un "tiempo de ejecución esperado": verificamos cada valor posible de las decisiones aleatorias y su probabilidad, y el "tiempo de ejecución esperado" es el promedio ponderado del tiempo de ejecución para cada combinación de decisiones aleatorias , pero aún para una entrada fija.

Por lo tanto, calculamos el "tiempo de ejecución esperado" para cada entrada posible, y para obtener el "tiempo de ejecución esperado en el peor de los casos", encontramos la única entrada posible donde el tiempo de ejecución esperado es peor. Y aparentemente mostraron que el peor de los casos para el "tiempo de ejecución esperado" es simplemente O (n log n). No me sorprendería si solo elegir el primer pivote al azar cambiaría el tiempo de ejecución esperado del peor de los casos a o (n ^ 2) (pequeño o en lugar de Big O), porque solo unos pocos de n pivotes conducirán al peor de los casos comportamiento.

Tenga en cuenta que hay dos cosas para superar las expectativas / promedio: la permutación de entrada y los pivotes (uno por partición).

$n$$\Theta(n \log n)$

$\Theta(n \log n)$

En pocas palabras, verifique su (s) fuente (s) para qué implementación usan y qué cantidad consideran aleatoria o resp. arreglado en su análisis.

$O(n^2)$

El peor caso para el ordenamiento rápido aleatorio son los mismos elementos que la entrada. Ej: 2,2,2,2,2,2

$T(n) = T(n-1) + n$$O(n^2)$