quicksort e inserción ordenar el tiempo de espera esperado híbrido

Question

Estoy aprendiendo CLRS 3ª edición y esta es una de las preguntas más difíciles que he encontrado junto con su respuesta como un servicio para todos.

7.4-5 podemos mejorar el tiempo de ejecución de la ordenación rápida en la práctica mediante el aprovechamiento del tiempo rápida ejecución de la ordenación por inserción cuando su entrada es “casi” ordenadas. Al llamar al quicksort en un subcampo con menos de k elementos, simplemente devuelva sin ordenando el subcampo. Después de que la llamada de nivel superior al quicksort regrese, ejecute la ordenación de inserción en toda la matriz para finalizar el proceso de clasificación. Supongamos que este algoritmo de ordenación se ejecuta en el tiempo esperado O(nk+nlg(n/k)). ¿Cómo debemos elegir k, ambos en teoría y en la práctica?

Answer 1

Si evalúa la ecuación nlgn > nk + nlog(n/k) obtiene log k > k. Lo cual es imposible Por lo tanto, en teoría, no es posible. Pero en la práctica hay factores constantes relacionados con la ordenación por inserción y el quicksort. Eche un vistazo a la solución discutida en este pdf. Es posible que desee actualizar su respuesta. .

Answer 2

Una hoja tiene la misma probabilidad de ser del tamaño entre 1 a k.
Así que el tamaño esperado de una hoja es k/2.
Si el tamaño esperado de una hoja es k/2 entonces esperamos n/(k/2)=(2n)/k tales hojas.
Para simplificar digamos que esperamos n/k tales hojas y que el tamaño esperado de cada hoja es k.
El tiempo de ejecución esperado de INSERTION-SORT es O(n^2).
Encontramos que en el ejercicio 5.2-5 y el problema 2-4c.
Por lo tanto, el tiempo de ejecución esperado del uso de INSERTION-SORT es O((n/k)*(k^2))=O(nk).
Si esperamos que nuestros grupos de particiones sean del tamaño k, se espera que la altura del árbol de recursión sea lgn-lgk=lg(n/k), ya que esperamos detener lgk anteriormente.
Hay O(n) operaciones en cada nivel del árbol de recursión.
Eso nos lleva al O(nlg(n/k)).
Concluimos que el tiempo de ejecución esperado es O(nk+nlg(n/k)).

En teoría, debemos elegir k=lgn, ya que de esta manera obtenemos el mejor tiempo de ejecución esperado de O(nlgn).

En la práctica, debemos elegir k a uno de los valores en torno a lgn que nos da un mejor rendimiento que simplemente ejecutar RANDOMIZED-QUICKSORT.

La segunda parte de la respuesta utiliza la notación de O grande bastante bastante, por lo que para un picking más preciso de k, siga el enlace dado en la segunda respuesta por Ankush.

Answer 3

En realidad, la respuesta es k = 8.

El algoritmo que obtienes es la composición de dos funciones anónimas, una de las cuales es O(nk) y la otra que es O(n lg n/k). Esas funciones anónimas ocultan constantes de casos promedio. La ordenación por inserción se ejecuta en el tiempo n^2/4 en el caso promedio y el quicksort aleatorizado se ejecuta en 1.386 n lg n en el caso promedio. Queremos encontrar un valor de k que minimice el valor de nk/4 + 1.386(n lg n/k) que equivale a nk/4 + 1.386 n lg n - 1.386 n lg k. Esto significa encontrar el máximo de la función 1.386 lg k - k/4. Ese valor máximo ocurre en k = 8.