Selección aleatorizado

Question

El algoritmo de selección aleatoria es la siguiente:

Entrada: Una matriz $ A $ de $ n $ (distinta, por simplicidad) números y un número $ k \ in [n] $

Salida: El el "rango $ k $ element" de $ A $ (es decir, el que está en posición $ k $ Si $ A $ se solucionó)

Método:

• Si hay un elemento en $ A $, devolverlo
• Seleccione un elemento $ p $ (el "pivote") de manera uniforme al azar
• Calcular los conjuntos $ L = \ {a \ in A: a

  p \} $

• Si $ | L | \ Ge $ k, devuelva el rango $ k $ elemento de $ L $.
• En caso contrario, devolver el rango $ k - | L | $ elemento de $ R $

Me pidieron la siguiente pregunta:

Supongamos que $ k = n / 2 $, por lo que busca la mediana, y dejar que \ alpha \ en (1 / 2,1) $ $ ser una constante. ¿Cuál es la probabilidad de que, en la primera llamada recursiva, la conjunto que contiene la mediana tiene un tamaño como máximo $ \ alpha $ n?

I se le dijo que la respuesta es de $ 2 \ alpha - 1 $, con la justificación "El pivote seleccionado debe estar entre $ 1- \ alpha $ y $ \ alpha veces $ la matriz original"

¿Por qué? Como $ \ alpha \ in (0,5, 1) $, cualquiera que sea elemento se elige como pivote es más grande o más pequeño que más de la mitad de los elementos originales. La mediana siempre se encuentra en el subconjunto más grande, debido a que los elementos en el subconjunto con particiones son siempre menor que el pivote.

Si las mentiras de pivote en la primera mitad de la matriz original (menos de la mitad de ellos), la mediana seguramente estar en el medio segundo más grande, porque una vez que se encuentra la mediana, que debe estar en la posición media de la matriz, y todo antes de que el pivote es menor a medida que se ha dicho.

Si las mentiras de pivote en la segunda mitad de la matriz original (más de la mitad de los elementos), la mediana seguramente primera mitad de grande, por la misma razón, todo antes de que el pivote se considera menor.

Ejemplo:

3 4 5 8 7 9 2 1 6 10

La mediana es 5.

supone que el pivote elegido es 2. Así que después de la primera iteración, se convierte en:

1 2 .... parte más grande ....

Sólo 1 y 2 se intercambian después de la primera iteración. Número 5 (la mediana) se encuentra todavía en la primera media mayor (accroding al pivote 2). El punto es, la mediana de las mentiras siempre en mayor media, ¿cómo puede tener la oportunidad de estancia en un subconjunto más pequeño?

Answer 1

Supongamos que su matriz tiene $ $ n elementos. Como usted ha señalado, la mediana es siempre en la parte más grande después de la primera partición. La parte más grande tiene un tamaño como máximo $ \ alpha $ n si es la parte más pequeña tiene un tamaño de al menos $ (1- \ alpha) n $. Esto sucede cuando usted escoge un pivote que no es uno de los más pequeños o más grande $ (1- \ alpha) n elementos $. Debido a que $ \ alpha> de 1/2 $, usted sabe que son conjuntos disjuntos, por lo que la probabilidad de acertar uno de los malos pivotes es sólo $ 2 - 2 \ alpha $, y $ 1- 2 + 2 \ alpha = 2 \ alpha - 1 $.