bc1435 – Mediana

O problema de determinar a mediana de um vetor qualquer com {n} inteiros é descobrir o {\lceil n/2 \rceil}-ésimo menor elemento do vetor, isto é, o elemento da posição {\lceil n/2 \rceil} quando consideramos o vetor ordenado. Uma solução fácil é ordenar o vetor, sabemos que isso consome {\Omega(n\log n)} instruções no pior caso. Sabemos encontrar o menor elemento e maior elemento em tempo \Theta (n). É possível fazer melhor no caso da mediana?  

Vamos enunciar o problema de um modo mais genérico:

Problema da Seleção

Instância: Uma sequência A de n inteiros (distintos) e um inteiro k \in [1 .. n].

Resposta: O elemento x \in A que é maior do que exatamente k -1 outros elementos de A.

Uma solução para o problema da seleção resolve, claramente, o problema da mediana. Curiosamente, se temos uma solução para o problema da mediana, também temos uma solução para o problema da seleção.

Exercício 1 Suponha que Mediana (A[1..n]) é um algoritmo que devolve a posição da mediana do vetor A. Escreva um algoritmo que usa Mediana para resolver o problema da seleção.

Uma solução elegante para o problema da mediana usa o algoritmo de partição do quicksort. Lembremos que

 Partição {(A[i..f])} 

  Dado um vetor {A[i..f]} de números inteiros, com
          {i < f} e A[i-1] \leq A[i..f] \leq A[f+1] . 
  Devolve d \in [i..f] e os elementos de A  rearranjados de modo que 
          A[i..d-1] \leq A[d] \leq A[d+1..f].

se {d} dado por Partição é a mediana então estamos feitos; se {d} é maior que a mediana então continuamos em {A[1..d-1]} senão continuamos pela procura do {(\lceil n/2 \rceil -d)}-ésimo menor elemento de {A[d+1..n]}. Podemos generalizar essa solução para o problema da seleção

 Seleção-Partição(A[1..n],k) 

  Dado um vetor A[1..n] de números inteiros e um inteiro k entre 1 e n
  Devolve o k-ésimo menor elemento de A.

1 Se (n=1) devolva(A[1])
2 Senão {
3   d <- Partição (A[1..n]) 
4   Se (k < d) 
5            devolva Seleção-Partição(A[1..d-1],k) 
6   Senão Se (k > d) 
7            devolva Seleção-Partição(A[d+1..n],k-d) 
8         Senão devolva(A[p]) }

Esse algoritmo tem custo quadrático no pior caso. Vamos contar o número de comparações feitas com uma entrada de temanho n no pior caso. Notemos que o número de comparações é proporcional ao número de instruções básicas que o algoritmo executa.

No pior caso, d na linha 3 é sempre a primeira posição do vetor (i) de modo que o número de comprações é

{\displaystyle T(n) = T(n-1) +(n+1)}, portanto T(n) = O(n^2).

Esse custo pode ser melhorado se conseguirmos escolher bem um pivô de modo que a partição seja mais equilibrada. De fato se o tamanho do subproblema na recursão for < \alpha n para alguma constante \alpha < 1, então

{\displaystyle T(n) \leq T(\alpha n) +(n+1)}, portanto T(n) = O(n).

De fato, iterando a recurrência i vezes

\displaystyle \begin{array}{rcl} T(n) &\leq& T(\alpha^i n) + \alpha^{i-1} n + \cdots + \alpha n + i \\ &\leq& T(\alpha^i n) + \frac{1-\alpha^{i}}{1-\alpha} n + i \end{array}

e tomando i da ordem de \log_{1/\alpha}n temos T(n) \leq c( 1 + n +\log_{1/\alpha}n), portanto T(n) = O(n).

Um modo de escolher o pivô que podemos adotar é como a que foi feita no quicksort probabilístico: escolhemos um elemento do vetor aleatoriamente para ser o pivô. Tal pivô é bom se não for dos 10% menores elementos do vetor nem dos 10% maiores elementos do vetor. A probabilidade de sortear um pivô bom é {4/5} e o número esperado de sorteios de pivôs não-bons entre dois bons consecutivos é no máximo {2}. Se todas as escolhas consecutivas são boas então a cada pivotamento pelo menos 10% do vetor é descartado logo o número de comparações executadas é

\displaystyle \begin{array}{rcl} T(n) &\leq& T( 9n/10 ) + n \\ &\leq& T( 81n/100 ) + n + 9n/10\\ &\vdots& \cdots\\ &\leq & ( 1 + 9/10 +(9/10)^2 +(9/10)^3+ \cdots) n = 10n \end{array}

logo {T(n) =O(n)} (verifique usando indução).

Seleção_probabilístico

Seleção_probabilístico (A[1..n],k)

   Dados um vetor de inteiros A[1..n] um inteiro k entre 1 e n.
   Determina o k-ésimo menor elemento de A. 

1 Se (n=1) devolva(A[1])
2 Senão {
3   sorteie r em [1..n]; A[r] <-> A[i] 
4   p <- Partição (A[1..n])
5   Se (k <= p) 
6     devolva(Seleção_probabilístico(A[1..p],k) )
7   Senão 
8     devolva(Seleção_probabilístico(A[p+1..n],p-k))}

 

— Algoritmo determinístico de complexidade linear —

O algoritmo abaixo determina a mediana de um vetor em tempo linear e foi descoberto por Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest, and Bob Tarjan no início dos anos ’70 [ Linear time bounds for median computations].

Ideia geral do algoritmo SELEÇÃO:
1. Divida os n elementos da entrada em {\lceil n/5 \rceil} grupos de cinco elementos cada (e no máximo um grupo consistindo dos elementos restantes);

2. Descubra a mediana em cada um dos {\lceil n/5\rceil} grupos;

3. Use SELEÇÃO recursivamente para descobrir a mediana A[mdm] das {\lceil n/5 \rceil} medianas;

4. Particione a entrada usando A[mdm] como pivô;

5. Se k <= mdm use SELEÇÃO recursivamente em A[1..mdm] para achar o k-ésimo menor;

6. Senão use SELEÇÃO recursivamente em A[mdm..n] para achar o (k-mdm)-ésimo menor.


 

Detalhamento:

Seleção 

Seleção (A[1..n],k) 

Dado um vetor A[1..n] e inteiros e um inteiro k entre 1 e n
Devolve o k-ésimo menor elemento de A

 
1. Se (n <= 25) use força bruta; 
2. Senão { 
3.   m <- {\lceil}n/5{\rceil} 
4.   Para i de 1 até m 
        B[i] <- Seleção-força-bruta(A[5i- 4..5i],3) 
6.   mdm <- Seleção(B[1..m],{\lfloor}m/2{\rfloor})
7.   A[1] <-> A[mdm]
8.   d <- Partição(A[1..n])
9.   Se (k < d) Devolva(Seleção(A[1..d-1],k))
10.  Senão Se (k > d) Devolva(Seleção(A[d+1..n],k-d))
10.       Senão Devolva(A[mdm])}. 

A ideia fundamental para a eficiência dessa algoritmo é que os dois subvetores das instâncias recursivas não serão nem muito grande. A mediana-das-medianas ({mdm}) é maior do que {\lceil \lceil n / 5 \rceil / 2\rceil - 1\approx n/10} medianas, e cada uma desses medianas é maior do que dois outros elementos em seu grupo.

selecao1

Em outras palavras, a mediana-das-medianas é maior do que pelo menos {3n/10} do vetor de entrada.

selecao2

Simetricamente, {mdm} é menor do que, pelo menos {3n/10} elementos da entrada. Assim, no pior caso, a chamada recursiva final e sobre um vetor de tamanho {\leq n-3n/10= 7n/10}.

Determinar a mediana de cada grupo usa no máximo {6} comparações e a partição usa no máximo {n+1} comparações portanto, o total é de no máximo {11n/5} comparações mais as comparações feitas nas chamadas recursivas, i.e., o número de comparações para entradas de tamanho {n} no pior caso satisfaz

\displaystyle T(n) \leq T(7n/10) + T(n/5) + 11/5n

cuja solução é O(n).

–Máximo e mínimo–

Determinar o mínimo de um sequência A de n inteiros é é mais fácil que Seleção(A[1..n],1), pode ser feito usando exatamente n-1 comparações:examinar cada elemento do conjunto, e armazenar o menor elemento visto até agora.

Encontrar o máximo também é realizado com {n- 1} comparações. É este o melhor que podemos fazer? Sim, o seguinte argumento estabelece um limitante inferior de {n - 1} comparações para o problema de determinar o mínimo: modelamos o comportamento de qualquer algoritmo que determina o mínimo como um torneio entre os elementos. Cada comparação {x_i<x_j\mathrm{?}} é uma partida no torneio em que o menor dos dois elementos ganha. A observação importante é que todos os elementos, exceto o vencedor deve perder pelo menos um jogo. Assim, {n -1} comparações são necessárias para determinar o mínimo.

Quantas comparações são necessárias para determinar o máximo e o mínimo de uma sequência {A=(x_1,x_2,\dots,x_n)} de {n} números inteiros?

 

 Exercício 2 Descreva um algoritmo que, no pior caso, determina o máximo e o mínimo de uma sequência de {n} números, simultaneamente, e que executa no máximo {3\lceil n/2 \rceil} comparações.

Exercício 3 Mostre que {\lceil 3n / 2 \rceil- 2} comparações são necessárias no pior caso para encontrar tanto o máximo e o mínimo de {n} números. (Dica: Considere quantos números são potencialmente ou o máximo ou mínimo, e investigue como uma comparação afeta essas contagens.)

Exercicío 4 Mostre que o segundo menor de {n} elementos pode ser encontrado com {n + \log_2 (n) - 2} comparações no pior caso.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s