Este página trata do problema da encontrar a mediana de um conjunto.
(Não confunda mediana com média.
Por exemplo,
a média de {1, 2, 99} é 51,
enquanto a mediana é 2.)
Também trata do problema mais geral de encontrar o i-ésimo menor elemento do conjunto.
É fácil resolver o problema em tempo linearítmico;
mas gostaríamos de resolver o problema em tempo
linear.
Mostraremos como fazer isso em média
.
A página é inspirada no capítulo 9 de CLRS.
Dado um conjunto S de números, o posto (= rank) de um elemento x de S é número de elementos de S que são menores ou iguais a x, ou seja, a cardinalidade do conjunto { s ∈ S : s ≤ x }. Se os elementos de S são s1, s2, … , sn em ordem crescente então o posto de si é i. (Convém não esquecer que, como em qualquer conjunto, os elementos de S são distintos dois a dois.)
O i-ésimo menor elemento de um conjunto S é o elemento de posto i. Por exemplo, o 1-ésimo menor elemento de S é o mínimo de S e o ⎮S⎮-ésimo menor elemento é o máximo de S.
A mediana (= median) de um conjunto S com n elementos é o ⌊(n+1)/2⌋-ésimo menor elemento de S. (Eu poderia ter adotado como mediana o ⌈(n+1)/2⌉-ésimo menor elemento; isso só faria diferença quando n é par.)
Nossos conjuntos serão representados por vetores com elementos distintos dois a dois, ou seja, sem elementos repetidos. (É bem verdade que quase tudo se aplica igualmente bem a vetores com elementos repetidos, mas a discussão fica mais simples se os elementos forem distintos dois a dois.)
Problema da mediana: Encontrar a mediana de um vetor A[p .. r] sem elementos repetidos.
Problema da mediana generalizada: Dado um vetor A[p .. r] sem elementos repetidos e um número natural i, encontrar o i-ésimo menor elemento do vetor.
É fácil resolver o problema em Ο(n lg n) unidades de tempo, sendo n o número de elementos do vetor: basta rearranjar A[p .. r] em ordem crescente e pinçar o elemento A[p + i − 1]. O desafio é obter um algoritmo mais rápido.
Exemplo A. No exemplo a seguir, o quarto menor elemento do vetor é 41, o sétimo menor elemento é 66, e a mediana é 55.
| 33 | 44 | 55 | 77 | 95 | 99 | 22 | 25 | 41 | 66 | 88 | 89 |
a mediana de um conjunto de n números é o ⌊n/2⌋-ésimo menor elemento do conjunto.
A mediana de A[1 .. n] é A[⌈n/2⌉].
Começamos por estudar um algoritmo que, no pior caso, é pior que ordenar-e-pinçar. Embora ruim, ele servirá de base para um algoritmo melhor, a ser estudado na próxima seção.
O algoritmo Select recebe um vetor A[p .. r] sem elementos repetidos e um número natural i e devolve o i-ésimo menor elemento do vetor. Vamos supor que 1 ≤ i ≤ r−p+1 (e portanto p ≤ r), pois do contrário a instância do problema não tem solução.
| Select (A, p, r, i) ▷ 1 ≤ i ≤ r−p+1 |
| 1 . se p = r |
| 2 .ooo devolva A[p] e pare |
| 3 . q := Divide (A, p, r) ▷ p ≤ q ≤ r |
| 4 . k := q − p + 1 |
| 5 . se i = k |
| 6 .ooo devolva A[q] e pare |
| 7 . se i < k |
| 8 .ooo devolva Select (A, p, q − 1, i) e pare |
| 9 . devolva Select (A, q + 1, r, i − k) |
Na linha 3, o algoritmo invoca a rotina Divide da página Ordenação: Quicksort, que rearranja o vetor e devolve um índice q tal que A[p .. q−1] < A[q] < A[q+1 .. r] (as duas desigualdades são estritas pois o vetor não tem elementos repetidos são distintos). Observe que nas linhas 8 e 9 as condições para a invocação de Select estão satisfeitas. Observe também que as instâncias de que essas linhas tratam são menores que a instância original.
Prova da correção do algoritmo. Se p = r então i = 1 e portanto o algoritmo devolve a resposta correta na linha 2. Agora suponha que p < r. Depois da linha 3, temos A[p .. q−1] < A[q] < A[q+1 .. r]. Depois da linha 4, k é o número de elementos de A[p .. q].
O algoritmo Select usa o método da divisão e conquista. A fase da divisão — executada por Divide — é a que consome mais tempo. A fase da conquista consiste nas duas chamadas recursivas, linhas 8 e 9. A fase da combinação é vazia.
Exemplo B. A figura faz o rastreamento da execução do algoritmo Select ao procurar pelo 7-o menor elemento de um vetor.
[33 44 55 77 95 99 22 25 41 66 88 89] [33 44 55 77 22 25 41 66 88] 89 [95 99] [33 44 55 77 22 25 41 66] 88 89 [95 99] [33 44 55 22 25 41] 66 [77] 88 89 [95 99]
O 7-o menor elemento do vetor é 66. (Isso foi detectado na linha 6 do algoritmo.)
Convém medir o consumo de tempo de Select indiretamente,
contando o número de comparações entre elementos do vetor
como já fizemos ao estudar o Quicksort.
Para simplificar, diremos simplesmente comparações
,
deixando a expressão entre elementos do vetor
subentendida.
Essas comparações ocorrem todas na linha 4 da rotina Divide,
que faz exatamente m − 1 comparações
quando recebe um vetor com m elementos.
Desempenho no pior caso. Seja n = r−p+1 o número de elementos do vetor e denote por P(n) o número de comparações no pior caso. A intuição sugere que o pior caso acontece quando toda execução de Divide faz uma divisão desequilibrada do vetor. Mais precisamente, o pior caso acontece quando (1) a linha 6 nunca é executada, (2) depois de cada execução da linha 3, q vale p (e portanto a linha 9 é executada) ou vale r (e portanto a linha 8 é executada). Nesse caso, P(n) satisfaz a recorrência
| P(n) = P(n−1) + n − 1 . | (A) |
O termo P(n−1) representa o número de comparações implícito nas linhas 8 e 9 e o termo n − 1 é o número de comparações em Divide. A recorrência pode ser facilmente desenrolada:
| P(n) | = | P(n−1) + n − 1 |
| = | P(n−2) + (n − 2) + (n − 1) | |
| = | P(n−3) + (n − 3) + (n − 2) + (n − 1) | |
| ⋮ | ||
| = | P(1) + 1 + 2 + … + (n − 2) + (n − 1) | |
| = | n(n−1)/2 |
pois P(1) = 0. (Verifique por indução!) Logo, P(n) = Θ(n²).
Como o consumo de tempo é proporcional ao número de comparações, concluímos que o algoritmo Select é quadrático no pior caso. Esse desempenho é pior que o trivial ordenar-e-pinçar.
Desempenho no melhor caso. No melhor caso, Select executa a linha 3 uma única vez e termina na linha 6. Assim, o algoritmo faz apenas n − 1 comparações.
Uma forma menos radical de melhor caso é aquela em que a linha 6 nunca é executada e todas as execuções da linha 3 produzem uma divisão equilibrada do vetor, deixando metade dos elementos de um lado e metade do outro. Nesse caso, o número M(n) de comparações satisfaz a recorrência
| M(n) = M(⌊(n−1)/2⌋) + n − 1 . | (B) |
Para tentar obter uma pista da solução dessa recorrência, vamos resolver a recorrência mais simples M(n) = M(n/2) + n − 1:
| M(n) | = | M(n/2) + n − 1 |
| = | M(n/4) + n/2 − 1 + n − 1 | |
| = | M(n/4) + n/2 + n − 2 | |
| = | M(n/8) + n/4 + n/2 + n − 3 | |
| = | M(n/2i) + n/2i-1 + n/2i-2 + … + n/2i-i − i | |
| = | M(n/2i) + 21n/2i + 22n/2i + … + 2in/2i − i | |
| = | M(n/2i) + n (21 + 22 + … + 2i) / 2i − i | |
| = | M(n/2i) + n (2i+1 − 2) / 2i − i |
(veja o Apêndice). Vamos imaginar que os valores de n são potências de 2. Então, quando i atingir lg n, teremos M(n) = 2 (n − 1) − lg n , pois M(1) = 0. Resumindo: M(n) = Θ(n).
É possível verificar diretamente que a solução M(n) da recorrência original (B) também está em Θ(n). O Teorema Mestre (veja a página Recorrências) também confirma que M(n) = Θ(n). Logo o algoritmo Select é linear no melhor caso.
Desempenho em um caso típico.
Mesmo que a linha 3 não divida A[p .. r]
de maneira perfeitamente equilibrada,
o algoritmo Select continua linear
se todas as divisões
deixarem uma porcentagem
dos elementos do vetor de um lado
e a porcentagem complementar do outro,
como acontece com o algoritmo Quicksort.
Isso sugere que, em média
,
o algoritmo Select é linear.
P(n) = maxh P(h) + n − 1 ,
com max tomado sobre todos os valores de h
no intervalo 1 .. n−1.
(Os casos h = 0 e h = n
não acontecem porque nem o vetor A[p .. q−1]
na linha 8 nem o vetor A[q+1 .. r]
na linha 9 são vazios.)
(Compare o P(h)
com o P(i−1) +
P(n−i)
na recorrência correspondente da página Ordenação: Quicksort.)
Mostre que P(n) = Ο(n²).
Mostre que P(n) = Ω(n²).
A seção anterior mostrou que o algoritmo Select tem mau desempenho quando a linha 3 divide o vetor de maneira sistematicamente muito desequilibrada. Isso acontece quando o pivô na rotina Divide é sistematicamente muito pequeno ou muito grande. Para evitar essa situação extrema, é uma boa ideia escolher o pivô aleatoriamente, como já fizemos na versão aleatorizada do Quicksort. O algoritmo Rand-Select faz isso. Ele recebe um vetor A[p .. r] sem elementos repetidos e um número natural i no intervalo 1 .. r−p+1 e devolve o i-ésimo menor elemento do vetor.
| Rand-Select (A, p, r, i) ▷ 1 ≤ i ≤ r−p+1 |
| 1 . se p = r |
| 2 .ooo devolva A[p] e pare |
| 3 . q := Rand-Divide (A, p, r) ▷ p ≤ q ≤ r |
| 4 . k := q − p + 1 |
| 5 . se i = k |
| 6 .ooo devolva A[q] e pare |
| 7 . se i < k |
| 8 .ooo devolva Rand-Select (A, p, q − 1, i) e pare |
| 9 . devolva Rand-Select (A, q + 1, r, i − k) |
Não faz sentido discutir o desempenho de pior caso nem o de melhor caso de Rand-Quicksort. Devemos tratar do desempenho esperado (no sentido que essa palavra tem na teoria das probabilidades). Como já fizemos na seção anterior, vamos medir o consumo de tempo pelo número de comparações (linha 4 de Divide).
O ponto de partida para o cálculo do número esperado de comparações é a seguinte observação: o número de comparações que o algoritmo executa não depende dos valores dos elementos do vetor A[p .. r] mas apenas da posição de seu menor elemento, da posição do segundo menor elemento, da posição do terceiro menor elemento, etc. Assim, por exemplo, o vetor [88 55 99 22] é equivalente ao vetor [3 2 4 1]. Podemos, portanto, restringir nossa atenção aos vetores que são permutações de 1 .. n, sendo n = r−p+1.
Exemplo C: A tabela mostra o número esperado de comparações para todas as n! permutações de 1 .. n supondo que a linha 6 nunca é executada, que a linha 8 é executada se q − p > r − q e que a linha 9 é executada q − p < r − q.
| n | comparações | ||
| 1 | 0 | / | 1 |
| 2 | 2 | / | 2 |
| 3 | 16 | / | 6 |
| 4 | 116 | / | 24 |
| 5 | 864 | / | 120 |
| 6 | 7128 | / | 720 |
| 7 | 63744 | / | 5040 |
| 8 | 630816 | / | 40320 |
Suponha que A[p .. r] é uma permutação aleatória de 1 .. n e seja E(n) o número esperado de comparações que Rand-Select executa supondo que todas as n! permutações são igualmente prováveis. (Em outras palavras, E(n) é o número médio de comparações para as n! permutações de 1 .. n. Veja a página Análise probabilística e algoritmos aleatorizados.) Um cálculo probabilístico mostra que E(n) satisfaz a recorrência
| (C) |
(Veja a dedução da recorrência na seção 9.2 de CLRS e compare com a recorrência correspondente do Rand-Quicksort.) De acordo com a recorrência (C), E(2) ≤ (2/2) E(1) + 1, E(3) ≤ (2/3) (E(1) + E(2)) + 2, E(4) ≤ (2/4) (E(2) + E(3)) + 3, e assim por diante. Como E(1) = 0, temos
E(n) ≤ 8n
para todo n ≥ 1. Isso não surpreende em face da discussão do desempenho típico de Select (sem a aleatorização).
Exemplo D: A tabela mostra a cota superior (C) para alguns valores de n. Verifique esses números! Escreva os números em notação ponto-flutuante.
| n | (C) | ||
| 1 | 0 | / | 1 |
| 2 | 2 | / | 2 |
| 3 | 16 | / | 6 |
| 4 | 116 | / | 24 |
| 5 | 888 | / | 120 |
| 6 | 7176 | / | 720 |
| 7 | 66048 | / | 5040 |
| 8 | 638112 | / | 40320 |
Como o consumo de tempo de Rand-Select é proporcional ao número de comparações, concluímos que o consumo de tempo esperado do algoritmo é
Ο(n) .
antes depois comparações
[2 1 3] [2 1] 3 3
[1 3 2] [1] 2 [3] 2
Blum, Floyd, Pratt, Rivest, Tarjan
encontraram (1973)
um algoritmo linear
para o problema da mediana generalizada.
O algoritmo consome tempo Ο(n),
mesmo no pior caso,
mas é um tanto complexo
e a constante escondida sob a expressão
Ο(n)
é grande.