se me dio la siguiente pregunta en un libro de algoritmos:de combinación aleatoria especie
Supongamos una especie de combinación se implementa para dividir un archivo en una posición aleatoria, en lugar exactamente en el medio. ¿Cuántas comparaciones usaría ese método para ordenar n elementos en promedio?
Gracias.
que lo guíe hacia la respuesta, considere estas preguntas más específicas:
asumir la división es siempre al 10%, o el 25% o 75% o 90%. En cada caso: ¿cuál es el impacto en las profundidades de recursión? ¿Cuántas comparaciones deben ser por nivel de recursión?
Estoy parcialmente de acuerdo con @Armen, deberían ser comparables.
Pero: considere el caso cuando están divididos en el medio. Para fusionar dos listas de longitudes n, necesitaríamos 2*n - 1 comparaciones (a veces menos, pero consideraremos que se corrigió por simplicidad), cada una de ellas produciendo el siguiente valor. Habría log2(n) niveles de fusiones, que nos da aproximadamente n*log2(n) comparaciones.
considerando ahora el caso al azar-split: El número máximo de comparations necesarios para fusionar una lista de longitud n1 con uno de longitud n2 será n1 + n2 - 1. Sin embargo, el número promedio se acercará a él, porque incluso para la división más infeliz 1 y n-1, necesitaremos un promedio de n/2 comparaciones. Entonces, podemos considerar que el costo de fusión por nivel será el mismo que en el caso par.
La diferencia es que, en casos aleatorios, el número de niveles será mayor, y podemos considerar que n para el siguiente nivel sería max(n1, n2) en lugar de n/2. Este max(n1, n2) tenderá a ser 3*n/4, que nos da la fórmula aproximada
n*log43(n) // where log43 is log in base 4/3
que nos da
n * log2(n)/log2(4/3) ~= 2.4 * n * log2(n)
Este resultado es aún más grande que la correcta ya que ignora que la lista pequeño tendrá menos niveles, pero debe ser lo suficientemente cerca. Supongo que la respuesta correcta será el número de comparations en promedio se duplicará
Usted puede obtener una cota superior de 2n * H_ {n - 1} < = 2n ln n usando el hecho de que la fusión de dos listas de longitud total n costos como máximo n comparaciones. El análisis es similar al de la conexión rápida aleatorizada (consulte http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf).
Primero, supongamos que dividimos una lista de longitud n en 2 listas L y R. Cargaremos el primer elemento de R para una comparación con todos los elementos de L, y el último elemento de L para una comparación contra todos los elementos de R. Aunque estas pueden no ser las comparaciones exactas que se ejecutan, el número total de comparaciones que estamos cobrando es n como se requiere.
Esto maneja un nivel de recursión, pero ¿qué pasa con el resto? Procedemos concentrándonos solo en las comparaciones de "derecha a izquierda" que ocurren entre el primer elemento de R y cada elemento de L en todos los niveles de recursión (por simetría, esto será la mitad del total real esperado).La probabilidad de que el elemento j-ésimo se compare con el elemento i-ésimo es 1/(j - i) donde j> i. Para ver esto, tenga en cuenta que el elemento j se compara con el elemento i exactamente cuando es el primer elemento elegido como un "elemento de división" entre el conjunto {i + 1, ..., j}. Es decir, los elementos i y j se dividen en dos listas tan pronto como la lista en la que se encuentran se divide en algún elemento de {i + 1, ..., j}, y el elemento j se carga para una comparación con i exactamente cuando el elemento j es el elemento que se elige de este conjunto.
Por lo tanto, el número total esperado de comparaciones que involucran j es como máximo H_n (es decir, 1 + 1/2 + 1/3 ..., donde el número de términos es como máximo n - 1). Sumando a través de todas las posibles j se obtiene n * H_ {n - 1}. Esto solo contó las comparaciones de "derecha a izquierda", por lo que el límite superior final es 2n * H_ {n - 1}.