quicksort aleatorizado: ¿probabilidad de comparación de dos elementos?

Question

Estoy leyendo "Probability and Computing" por M.Mitzenmacher y E.Upfal. Tengo problemas para entender cómo se calcula la probabilidad de comparación de dos elementos.

Entrada: lista ordenada (y1, y2, ..., yN) de los números. Estamos buscando un elemento pivote (aleatoriamente). Pregunta: ¿cuál es la probabilidad de que se comparen dos elementos yi e yj (j> i)?

respuesta (de libro): yi y yj será comparado si cualquiera yi o yj serán seleccionados como pivote en primer sorteo de secuencia (yi, yi + 1, ..., yj-1, yj) . Entonces la probabilidad es: 2/(j-i + 1).

El problema para mí es la afirmación inicial: por ejemplo, levantar yi en el primer sorteo de toda la lista causará la comparación con yj (y viceversa) y la probabilidad es 2/n.

Por lo tanto, más bien la afirmación "inversa" es verdadera: ninguno de los elementos (yi + 1, ..., yj-1) se puede seleccionar antes de yi o yj, pero el tamaño del "grupo" no está fijo (en el primer dibujo, es N seguro, pero en el segundo es más pequeño).

¿Podría alguien explicar cómo los autores presentan una conclusión tan simplificada?

Edit1: algunas buenas almas pulieron mi publicación, gracias :-).

Editar2: la lista está ordenada inicialmente.

Answer 1

La respuesta dada por los autores es correcta, aunque todavía no veo cómo llegaron a la conclusión de manera fácil y rápida.

Let denote por L = j-i + 1. Los valores reales de jy no importan aquí, lo que importa es L. También denotemos por P (N, L) la probabilidad de comparar elemento yi y yj de secuencia ordenada de números de tamaño N.

Hechos:

• P (N, 2) = 1
• P (N, L) = 2/N + 1/N * (P (N-1, L) + P (N-2, L) + P (N-3, L) + ... + P (L, L))

Esta suma parece fea, pero después de dos pruebas, parece que el P (N, L) es probablemente igual a 2/L. Vamos a verifique:

• P (N, L = 2) = 1 = 2/2 = 2/L
• supongamos que P (N, L) = 2/L
• P (N + 1, L) = 2/(N + 1) + 1/(N + 1) * (P (N, L) + ... P (L, L)) = 2/(N + 1) + (N-L + 1) * 1/(N + 1) * 2/L = 2/L

Y como L = j-i + 1, obtenemos 2/(j-i + 1).

Answer 2

Quicksort funciona comparando cada elemento con el pivote: los más grandes que el pivote se colocan a la derecha del pivote, y los que no son más grandes a la izquierda (o al revés si desea un orden descendente, no lo hace no importa).

En cada paso, el pivote se elige de una secuencia (yi, yi+1, ..., yj). ¿Cuántos elementos hay en esta secuencia? j - i + 1 (creo que tuvo un error tipográfico, no puede ser y - i + 1).

Entonces la probabilidad de seleccionar uno de dos elementos específicos de esta lista es obviamente 2/(j - i + 1).

El problema para mí es el reclamo inicial: por ejemplo, levantar yi en el primer sorteo de toda la lista causará la comparación con yj (y viceversa) y la probabilidad es 2/n.

Picking yi hará que ser comparado con los otros j - i únicos elementos. ¿De dónde sacaste n? ¡Recuerde que su lista solo va desde yi hasta yj!

Editar:

La lectura de la pregunta de nuevo, yo lo encuentro un poco ambigua. La probabilidad de comparar dos elementos en el primer paso de la recursión es de hecho 2/n como usted dice, porque i y j son 1 y n. La probabilidad de comparar dos elementos en un paso recursivo desconocido es lo que expliqué anteriormente.