Medianas e Estatísticas
de Ordem
Marcela Quispe Cruz
[email protected]
Medianas e Estatísticas de
Ordem






o Problema da Seleção consiste em que dado um
conjunto A de n números distintos e um número i, 1 <= i
<= n, determinar qual é o i-ésimo menor elemento de A.
São casos particulares do problema da seleção:
O mínimo, o primeiro
O máximo, o ultimo
A mediana de um conjunto, onde i = 1, i = n e i = n/2,
respectivamente.
 Par
Impar
Um algoritmo para o problema da seleção deve de
alguma forma obter informação, ainda que parcial, sobre
a ordem dos elementos do conjunto.
Quantas comparações são
necessárias para determinar
ambos o mínimo e o máximo
?
Para determinar o mínimo n-1 comparações são
necessárias. O mesmo é certo para o máximo.
Por tanto, o numero deve ser 2n-2 para
determinar ambos.
De fato somente 3
comparações são
necessárias para encontrar ambos o mínimo e o
máximo
compara o menor com
min y o maior com
max
Seleção em tempo linear
esperado


Entrada: vetor A de números reais, os índices p e r que
delimitam inicio e fim do subvetor onde seria feita a seleção e
i, o índice do elemento procurado no vetor ordenado.
Saída: o i-ésimo menor elemento do vetor A.
RANDOMIZED-SELECT(A, p, r, i)
1 if p = r
2
then return A[p]
3 q ← RANDOMIZED-PARTITION(A, p, r)
 k de elementos no subarray
4 k←q-p+1
5 if i = k
 o valor pivô é a resposta
6
then return A[q]
7 elseif i < k
8
then return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
Ex. de PARTITION
PARTITION(A,p,r)
1 x = A[ r ] .................................
2 i = p - 1 ..................................
3 for j = p to r - 1 .........................
4 do if A[ j ] <= x .........................
5
then i = i + 1 .........................
6
trocar A[ i ] com A[ j ] ..........
7 trocar A[ i+1] com A[ r ] ..............
8 return i + 1 ...... ......... .............
Total: ( r – p ) e <= { 6 ( r – p ) + 6 }
ou seja lineal na longitude do array A[p..r]
RAMDOMIZED-PARTITION(A,p,r)
1 i = RAMDOM (p,r)
escolhe um i,
2 exchange A[p] <-> A[i]
p <= i <= r
3 return PARTITION(A,p,r)
e usamos A[i]
como pivot
Necessitamos mostrar que n é
suficientemente grande, esta
expressão é no maior cn/4-c/2-an ≥ 0
Se assumimos que T(n)=O(1) para
n<2c/(c-4a), temos T(n) = O(n). Nós
concluímos que qualquer ordem estatístico
e no particular a mediana pode ser
determinar em promedio em tempo lineal
Seleção em tempo linear pior
caso
O algoritmo de seleção com tempo de execução O(n) no pior caso seleciona o elemento
desejado particionando recursivamente o arranjo de entrada. Essa partição deve garantir
uma boa divisão desse arranjo.
O algoritmo SELECT determina o i-ésimo menor elemento de um arranjo de entrada com
n > 1 elementos, executando 5 etapas:
1.
2.
3.
4.
5.
Dividir os n elementos do arranjo de entrada em piso(n/5) grupos de 5
elementos cada e no máximo 1 grupo com menos de 5 elementos. O(n)
Encontrar a mediana dos teto(n/5) grupos, usando primeiro a ordenação
por inserção dos elementos do grupo para em seguida, escolher a
mediana dos grupos. O(n)
Usar o SELECT recursivamente para encontrar a mediana x das teto(n/5)
medianas encontradas. T(n/5)
Particionar o arranjo de entrada em torno da mediana de medianas x. Seja
k uma unidade maior que o número de elementos no lado de baixo da
partição, de forma que x seja o k-ésimo menor elemento e existam n – k
elementos no alto da partição. O(n)
Se i == k, retorne k. Caso contrário, usar o SELECT recursivamente para
encontrar o i-ésimo menor elemento no lado baixo da partição, se i <= k,
ou então o (i – k)-ésimo menor elemento no lado alto da partição, se i > k.
T( max( q - p, r - q ) )
pelo menos 1/2 dos teto(n/5) medianas
no step 2 são maiores que x,
ignorando o grupo no qual x pertence
e o grupo que tem quantidade menor que 5
elementos si 5 não divide n exatamente
Logo o número de elementos maiores
que x é pelo menos
Assumindo que T(n) é nãodecrescente isso implica que o
tempo usado pelo step 5 é não maior
Que T( 7n/10 + 6 )
Assumindo que a entrada com n<=140 usa tempo O(1).
Permita que a seja tal que os step 1,3,4 necessitem tempo
não maior que an vezes.
Assuma que T(n) é não decrementavel. Logo
provaremos por induçao que T(n)<=cn, para todo n>0.
Escolhendo c bastante grande que
Pela Hipotesis de Indução
ou
Posto que n >= 140 temos que n/(n-70)<2 por tanto isto seria
verdadeiro para c >= 20a e logo temos demonstrado que
T(20)<=cn para todo n >= 140 e: