Esto es para el auto-estudio. Esta pregunta es de Kenneth Rosen "Matemática Discreta y Sus Aplicaciones".
El quick sort es un algoritmo eficiente. Para ordenar $a_1,a_2,\ldots,a_n$, este algoritmo comienza por tomar el primer elemento $a_1$ y formando dos sublistas, la primera que contiene los elementos que están a menos de $a_1$, en el orden en que surgen, y la segunda contiene los elementos mayor que $a_1$, en el orden en que surgen. A continuación, $a_1$ es poner al final de la primera sublista. Este procedimiento se repite recursivamente para cada sublista, hasta que todas las sublistas contienen un elemento. La lista ordenada de $n$ artículos se obtiene mediante la combinación de las sublistas de uno de los elementos en el orden en que se producen.
En este ejercicio encontramos que el promedio de caso, la complejidad del algoritmo de ordenación rápida, asumiendo una distribución uniforme en el conjunto de las permutaciones.
a) sea X el número de comparaciones utilizado por el algoritmo de ordenación rápida para ordenar una lista de n distintos números enteros. Muestran que el número medio de comparaciones utilizado por el algoritmo de ordenación rápida es $E(X)$ (donde el espacio muestral es el conjunto de todos los $n!$ permutaciones de $n$ enteros).
b) Vamos a $I(j,k)$ el valor de la variable aleatoria que es igual a 1 si el $j^{th}$ elemento más pequeño y el $k^{th}$ último elemento de la lista inicial son cada vez comparado como el algoritmo de ordenación rápida ordena la lista y es igual a 0 en caso contrario. Mostrar que $X = \sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}$.
c) Mostrar que el $E(X) = \sum_{k=2}^{n} \sum_{j=1}^{k-1} p$ donde $p$ es la probabilidad de que el $j^{th}$ elemento más pequeño y el $k^{th}$ más pequeño elemento de la comparación.
d) Mostrar que $p$ ($j^{th}$ elemento más pequeño y el $k^{th}$ más pequeño elemento de comparación), donde $k > j$, es igual a $2/(k − j + 1)$.
Yo no tenía ningún problema en particular con las partes a, b y c.
Creo que he logrado entender partes de un, b, y c de.
Por una parte, esto parece obvio, a partir de la definición de valor esperado. E(X) es el valor medio del número de comparaciones, ponderada por la probabilidad de que la permutación tiene un orden en particular (que es $1/n!$).
Para la parte b, he comprobado que la suma de $\sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}$ da $I_{1,2} + I_{1,3} + I_{2,3} + I_{1,4} + I_{2,4} + I_{3,4}+\cdots+I_{n-1,n}$, es decir, da el valor de $I_{j,k}$ por cada combinación de $j$$k$. Así, suma 1 a cada par de números enteros que serán comparadas. Dado que la situación sólo dos enteros conseguir en comparación es cuando uno de ellos el que el primer elemento de la lista (también llamado el "pivote"), esto significa que estos dos números enteros se van cada uno por separado sublistas, de modo que no se puede comparar más (en otras palabras, cada par de enteros es comparado a la mayoría de una vez). Por lo tanto, tiene sentido decir que la mencionada suma dará $X$, el número total de comparaciones hechas por ordenación rápida.
Parte c también parece sencillo. El resultado se sigue de la linealidad del valor esperado (valor esperado de una suma es la suma de los valores esperados): $E(X) = E\left(\sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}\right) = \sum_{k=2}^{n}\sum_{j=1}^{k-1}E(I_{j,k})$. El valor de $E(I_{j,k})$ (el valor esperado de $I_{j,k}$) es de 1 veces la probabilidad de que $I_{j,k}$ obtiene el valor 1; la probabilidad de que $I_{j,k}$ obtiene el valor 1 es la probabilidad de que el $j^{th}$ elemento más pequeño y el $k^{th}$ más pequeño elemento de comparación, por lo $I_{j,k} = p$. Por eso, $E(X) = \sum_{k=2}^{n}\sum_{j=1}^{k-1}p$.
De la parte d que es donde me quedé atrapado.
Traté de razonar de la siguiente manera: dada una lista que va a ser ordenada por la ordenación rápida, dos enteros $a_j$ $a_k$ va a conseguir en comparación a sólo si uno de ellos es el pivote. También, si el número es menor que $a_k$ y mayor que $a_j$ es el pivote, $a_k$ $a_j$ va a ir para separar sublistas, por lo que nunca tendrá comparación. De lo contrario, si el pivote es mayor que el de $a_k$$a_j$, o menor que ellos, $a_j$ $a_k$ ambos van a la misma sublista, por lo que, en otra llamada recursiva del algoritmo, que aún puede conseguir en comparación.
Pero no estoy seguro de cómo muestran que la probabilidad de que el $j^{th}$ elemento más pequeño y el $k^{th}$ elemento más pequeño cada vez son comparados $2/(k − j + 1)$. Alguien podría dar una sugerencia? Yo preferiría una sugerencia a través de una solución completa, de modo que yo pueda discutir en los comentarios para rellenar los huecos.
