Este página é inspirada no capítulo 10 de CLR. Ela trata do problema da mediana e também do problema mais geral do i-ésimo menor elemento de um conjunto.
Dado um conjunto S de números, o i-ésimo menor elemento de S é o número x em S tal que o conjunto {s ∈ S : s ≤ x} tem exatamente i elementos. Se s1,s2,…,sn é uma enumeração dos elementos de S tal que s1 < s2 < … < sn, então o i-ésimo menor elemento é si. 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 de um conjunto S com n elementos é o ⌊(n+1)/2⌋-ésimo (veja definição de piso) menor elemento de S. (Eu poderia ter definido a mediana como o ⌈(n+1)/2⌉-ésimo menor elemento. Isso só faria diferença quando n fosse par.) (Não confunda mediana com média. Por exemplo, a média de {1,2,99} é 51, enquanto a mediana é 2.)
Nossos conjuntos serão representados por vetores cujos elementos são distintos dois a dois. (É 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.) Nesse contexto, as definições podem ser reescritas como segue.
O i-ésimo menor elemento de um vetor estritamente crescente A[1..n] é o número A[i]. De modo um pouco mais geral, o i-ésimo menor elemento de um vetor estritamente crescente A[p..r] é o número A[i−p+1]. De modo ainda mais geral, o i-ésimo menor elemento de um vetor A[p..r] sem elementos repetidos é o número x tal que x = A[k] para algum k e |{ j : A[j] ≤ x}| = i . Em particular, a mediana de um vetor A[p..r] sem elementos repetidos é o ⌊½(n+1)⌋-ésimo menor elemento do vetor.
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.
É claro que o problema tem solução se e somente se 1 ≤ i ≤ r−p+1.
É muito fácil resolver o problema em tempo Ο(n lg n), sendo n o número de elementos do vetor. O desafio está em obter um algoritmo mais rápido.
| 33 | 44 | 55 | 77 | 95 | 99 | 22 | 25 | 41 | 66 | 88 | 89 |
O quarto menor elemento do vetor é 41 e a mediana é 55.
Existem algoritmos que resolvem o problema da mediana generalizada em tempo Ο(n), mesmo no pior caso. Nesta página, vamos nos contentar com algo mais fraco mas muito prático: um algoritmo cujo consumo de tempo esperado é Ο(n). Tal como o Quicksort, o algoritmo usa o paradigma da divisão e conquista.
O algoritmo recebe um vetor A[p..r] sem elementos repetidos e um índice t no conjunto {p,…,r} e usa o Separe-Aleatorizado para encontrar o (t−p+1)-ésmo menor elemento do vetor:
| Selecione-Aleat (A, p, t, r) |
| 1 o se p = r |
| 2 oooo então devolva A[p] |
| 3 oooo senão q ← Separe-Aleatorizado (A, p, r) |
| 5 oooo senão se q ≥ t |
| 6 oooo senão ooo então devolva Selecione-Aleat (A, p, t, q) |
| 7 oooo senão ooo senão devolva Selecione-Aleat (A, q+1, t, r) |
(Observe que na linha 6 as condições para a invocação de Selecione-Aleat estão satisfeitas. De fato, A[p..q] tem menos elementos que A[p..r] e t pertence ao conjunto {p,…,q}. Algo análogo acontece na linha 7.)
Prova da correção do algoritmo: Seja n = r−p+1. Se n = 1 então temos t = p e portanto o algoritmo devolve a resposta correta na linha 2. Agora suponha que n > 1. Depois da linha 3 temos A[p..q] ≤ A[q+1..r].
Suponha que Selecione-Aleat é aplicado a um vetor com n elementos distintos dois a dois. Seja E(n) o consumo de tempo do esperado do algoritmo. Então
E(n) está em Ο(n) .
A prova deste fato é semelhante ao cálculo do consumo de tempo esperado do Quicksort-Aleatorizado. Se Separe-Aleatorizado consome n unidades de tempo e as demais operações consomem 1 unidade de tempo, E satisfaz a recorrência
| E(n) = 1 + n + | E(max(1,n−1)) + ∑0<i<n E(max(i,n−i)) |
| n |
e portanto temos E(n) ≤ 1+n + (E(n−1) + 2 ∑i E(i)) / n , com soma indo de i = ⌈n/2⌉ a i = n−1. Segue daí que E(n) = Ο(n) .
Existe um algoritmo que resolve o problema da mediana generalizada em tempo Ο(n), mesmo no pior caso. Mas o algoritmo é um tanto complexo.