Seleção Aleatória

14

O algoritmo de seleção aleatória é o seguinte:

Entrada: Uma matriz de n (distintos, para simplificar) números e um número k [ n ]Ank[n]

Saída: O " elemento da classificação " de A (ou seja, aquele na posição k se A foi classificado)kAkA

Método:

  • Se houver um elemento em , retorne-oA
  • Selecione um elemento (o "pivô") uniformemente aleatoriamentep
  • Calcule os conjuntos e R = { a A : a > p }L={aA:a<p}R={aA:a>p}
  • Se , regressar ao posto k elemento de L .|L|kkL
  • Caso contrário, retorne a classificação elemento de Rk|L|R

Foi-me feita a seguinte pergunta:

Suponha-se que , de modo que procura a mediana, e deixá- ct ( 1 / 2 , 1 ) ser uma constante. Qual é a probabilidade de que, na primeira chamada recursiva, o conjunto que contém a mediana tenha tamanho no máximo α n ?k=n/2α(1/2,1)αn

Disseram-me que a resposta é , com a justificativa "O pivô selecionado deve ficar entre 1 - α e α vezes a matriz original"2α11αα

Por quê? Como , qualquer elemento escolhido como pivô é maior ou menor que mais da metade dos elementos originais. A mediana sempre fica no sub-arranjo maior, porque os elementos no sub-arranjo particionado são sempre menores que o pivô.α(0.5,1)

Se o pivô estiver na primeira metade da matriz original (menos da metade deles), a mediana certamente estará na segunda metade maior, porque, uma vez encontrada a mediana, ela deve estar na posição intermediária da matriz e tudo antes do pivô é menor, como mencionado acima.

Se o pivô estiver na segunda metade da matriz original (mais da metade dos elementos), a mediana certamente segurará a primeira metade maior, pelo mesmo motivo, tudo antes do pivô ser considerado menor.

Exemplo:

3 4 5 8 7 9 2 1 6 10

A mediana é 5.

Suponhamos que o pivô escolhido seja 2. Portanto, após a primeira iteração, ele se torna:

1 2 .... parte maior ....

Somente 1e 2são trocados após a primeira iteração. O número 5 (a mediana) ainda está na primeira metade maior (chegando ao pivô 2). O ponto é que a mediana está sempre na metade superior, como pode ter a chance de permanecer em um sub-arranjo menor?

Amumu
fonte
Não assistimos à sua palestra, então, explique o método.
Raphael
Sem saber de qual algoritmo preciso você está falando, sua pergunta não é legível. Você parece usar em várias capacidades; Tentei editar, mas não sei se entendi o significado. Revise para que a pergunta fique clara. Votação para fechar até então. .5
Raphael
É um algoritmo de seleção usando o método randomizado, em oposição ao método determinístico.
Amumu 18/04
Existem várias maneiras de selecionar um elemento aleatoriamente.
Raphael
2
@ Amumu: Eu editei para descrever o algoritmo. Em um fórum como este, nem todo mundo saberá do que você está falando, e existe uma abordagem aleatória muito diferente da seleção, que é mais fácil de analisar.
Louis

Respostas:

12

Suponha que sua matriz tenha elementos. Como você observou, a mediana está sempre na parte maior após a primeira partição. A parte maior tem tamanho no máximo α n se a parte menor tiver tamanho pelo menos ( 1 - α ) n . Isso acontece quando você escolhe um pivô que não é um dos menores ou maiores ( 1 - α ) n elementos. Porque α > 1 / 2 , você sabe estes são conjuntos disjuntos, então a probabilidade de acertar um dos maus pivôs é apenas 2 - 2 α e 1 -nαn(1α)n(1α)nα>1/222α .12+2α=2α1

Louis
fonte
Obrigado pela resposta. Eu ainda tenho algumas coisas incertas. Então, o que α> 1/2 tem algo a ver com conjuntos disjuntos? Eu pensei que quando sempre temos conjuntos disjuntos com esse método, independentemente do tamanho do subarray.
Amumu 18/04
Porque faz , de modo que ( 1 - α ) n < n - ( 1 - α ) n . 1α<1/2(1α)n<n(1α)n
Louis
Apenas uma última coisa: o que o pivô ruim / bom tem a ver com isso? Até onde eu sei, o bom pivô geralmente está no intervalo de 25 a 75 (que divide as matrizes originais de 25% a 75%), e o ruim está fora desse intervalo, e o pior geralmente está no início ou no final do original. array. Mas isso?
Amumu 18/04
2
αnα=3/4O()α