Probabilidad de que dos elementos se comparen en Quicksort aleatorizado

Question

Estoy teniendo un problema en una parte específica del análisis de clasificación rápida aleatorizado.

Según el algoritmo de clasificación rápida aleatorizado, el pivote se elige del subconjunto dado en el que se llama de un índice aleatorio, en lugar de elegir un índice específico cada vez.

Ahora supongamos que le damos una matriz de tamaño, digamos $ n $ a nuestro algoritmo de Quicksort aleatorizado.

Ahora solicito que eche un vistazo a la prueba de LEMMA-7.1 en el texto que se da a continuación. Ahora, hemos dado una matriz a nuestro algoritmo que puede ser de cualquier permutación de los elementos, pero en el párrafo justo después de la prueba de $ LEMMA-7.1 $ .

¿Por qué el autor está considerando una instancia ordenada de nuestra matriz de entrada mientras realiza el análisis?

Además, si mira el texto después de la ecuación $ (7.2) $ donde ha justificado su lógica de encontrar la probabilidad de que $ z_i $ se comparará con $ z_j $ en nuestro algoritmo. Ahora, en que están considerando el subconjunto { $ z_i $ , ..., $ z_j $ }. No es este caso de comparación de $ z_i $ , $ z_j $ obteniendo demasiado específico si consideramos que Subconjunto específico solamente? Quiero decir que estamos utilizando un enfoque aleatorizado y la probabilidad de que la comparación podría derivarse utilizando un aspecto más más amplio, como una permutación de todos los casos posibles o menos.

que estamos usando un subconjunto específico y que demasiado ordenado no es convincente sobre cómo estamos obteniendo la probabilidad correcta para nuestro algoritmo ...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

y la probabilidad de $ 1 / (j-i + 1) $ -> total no. de elementos en el El subconjunto también se fija para específico $ i $ y $ j $

Al considerar la probabilidad de comparación de $ z_i $ , $ z_j $ , el subconjunto en el que Los dos elementos están ahí y que deben ser particionados pueden ser cualquier cosa (es decir, compuesta de cualquier elemento posible) y de cualquier tamaño (no solo $ j-i + 1 $ ) ...

puede ser la condición de aleatorización en realidad está tomando todo en Cuenta pero no lo estoy recibiendo. Por favor, puede explicarme la lógica que utilizan para encontrar dicha probabilidad y también, convencerme de que estamos encontrando correctamente la probabilidad de comparación.

para referencia Estoy adjuntando las páginas correspondientes de la introducción a los algoritmos 3RD-- CLRS

Answer 1

Una prueba muy simple: afirma que si hay números enteros con valores entre X e Y, y hay n ≥ 2 elementos en la matriz, entonces la probabilidad de que X e Y se comparan es 2 / (D + 2 ), independiente de n.

Prueba por inducción: si n= 2 entonces claramente D= 0, por lo que la reclamación es que X e Y se comparan con la probabilidad 2 / (0 + 2)= 1. Esto también es claramente correcto, ya que X e Y debe ser comparado.

Ahora que n ≥ 3. Para la primera partición, elegimos un pivote al azar. Cada elemento de matriz se compara contra el pivote, y no se hacen otras comparaciones. Entonces, si por coincidencia, elegimos X o Y como el pivote, X e Y se compararán. La probabilidad de eso es 2 / n. Si por coincidencia, elegimos uno de los elementos D con valores entre X e Y, entonces la partición se moverá x a una partición y y al otro, por lo que nunca se comparan. Si eligimos uno de los otros elementos N - D - 2, entonces X e Y terminan en la misma partición, y por inducción se compararán con la probabilidad 2 / (D + 2).

Por lo tanto, la probabilidad de que se comparen X e Y es

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

Eso es, por supuesto, el mismo resultado que el de Yuval, desde | J - I |= D + 1. La aleatorización hace que el análisis sea bastante fácil, si dijimos, por ejemplo, "si n> 5, luego escogemos 5 elementos al azar y elige la mediana de los 5 como el pivote", el análisis sería mucho más complejo.

ps. La prueba en el documento es mucho más fácil: a medida que particiona la matriz, $ x_i $ y $ x_j $ permanecer en la misma subpartición hasta que se use un pivote con i <= pivot <= j se usa. Si ese pivote es I o J, entonces $ x_i $ y $ x_j $ se comparan, de lo contrario no son comparado. Así que la posibilidad es 2 / (ABS (J-I) + 1).

Answer 2

La idea de la prueba es calcular, para cualquier dos elementos $ x, y $ en la matriz, la probabilidad de que se comparen en el algoritmo. Esta probabilidad podría depender potencialmente de toda la matriz. Sin embargo, resulta que puede calcular que solo se le otorga las estadísticas de pedidos de $ x, y $ , es decir, su orden relativa en la matriz ordenada. Si sabe que $ x $ es el $ i $ el elemento más pequeño de la matriz y ese $ y $ es el $ j $ el elemento más pequeño de la matriz, entonces la probabilidad de que $ x, y $ se comparan es $ \ frac {2} {| ji | +1} $ .

Este no es un caso especial, cada elemento $ x $ en la matriz es el $ i $ El elemento más pequeño, por algún valor de $ i $ . Esta es solo la información pertinente que nos permite calcular la probabilidad de que $ x $ y $ y $ son comparado.