Problema da Mediana

Problema da Mediana

Em teoria da probabilidade e em estatística, a mediana é uma medida de tendência central, um número que caracteriza as observações de uma determinada variável de tal forma que este número (a mediana) de um grupo de dados ordenados separa a metade inferior da amostra, população ou distribuição de probabilidade, da metade superior. Mais concretamente, 1/2 da população terá valores inferiores ou iguais à mediana e 1/2 da população terá valores superiores ou iguais à mediana.

Às vezes, a mediana é uma medida melhor que do que a média, pois esta é influenciada por valores extremos.

Para calcular a mediana de n números é fácil: basta ordená-los. Se n é impar então a mediana será encontrada no termo (n+1)/2. Se n é par então a mediana será a média dos termos n/2 e (n+2)/2. A principal desvantagem desta abordagem é que isto leva O (n log n) para ser executado e gostaríamos de alguma coisa de linear.

Vamos considerar um problema mais geral.

SELECTION

Entrada: Uma lista de número S, um inteiro k

Saída: O k-ésimo menor elemento de S

Um algoritmo de divisão e conquista para a seleção baseado no quicksort

Para um número v, imagine que a lista S será dividida em duas categorias: elementos menores que v, aqueles que são iguais ou maiores que v. Por exemplo, se o vetor

é dividido considerando v=13, os dois sub-vetores gerados serão

S_L = {2,5,8,1,11,5,4} |S_L| = 7

S_R = {13,21,36,20}    |S_R| = 4

A busca será reduzida para umas dessas listas. Se nós queremos o oitavo menor elemento de S,  nós sabemos que ele será o primeiro menor elemento de S_R.

A complexidade deste algoritmo no pior caso é O(n²) e no melhor caso é O(n). Suponha que a escolha randômica de v tem 50% de chance de ser boa. Quantos v’s nós precisamos escolher para que em média consigamos uma boa escolha? Vamos colocar isso de outra forma e utilizar o seguinte lema.

Lema: Em média com uma moeda honesta precisamos jogar a moeda duas vezes antes que uma “cara” seja vista.

Prova 1: Seja E o valor esperado de vezes de lançamentos antes que uma cara seja vista. Nós precisamos de apenas um lançamento se ele é cara. Se ele é coroa (que ocorre com probabilidade 1/2), nós precisamos repetir o processo. Portanto, , isto vale quando E = 2.

Prova 2: 

Portanto, depois de duas divisões em média, o vetor estará reduzido a no máximo ¾ do seu tamanho. Seja T(n) o tempo de execução esperado para um vetor de tamanho n, nós teremos

T(n) ≤ T(¾n ) + O(n)

A partir dessa recorrência, temos que T(n) = O(n)

int selection (int *a, int ini, int fim, int k){
 int pivotIndex, pivotValue,auxIndex;
 int i;
 pivotIndex = (ini+fim)/2;//não-randômico
 pivotValue = a[pivotIndex];
 swap(a[pivotIndex], a[fim]);
 auxIndex = ini;
 for(i = ini; i< fim;i++){
  if(a[i] < pivotValue){
   swap(a[auxIndex], a[i]);
   auxIndex = auxIndex+1;
  }
 }
 swap(a[auxIndex], a[fim]); 
 if(k == auxIndex) return a[k];
 else if (k < auxIndex ) return selection(a, ini, auxIndex-1,k);
 else return selection(a,auxIndex+1, fim, k);
}

Exercício 1

Problema da localização da agência postal unidimensional

Temos n números reais a₁,…,a_n que representam as localizações de alguns pontos . Desejamos encontrar um número a (não necessariamente um dos números da entrada) que minimize o somatório das distâncias entre todos os números a_i e o número escolhido  a.

Mostre que a mediana é a melhor solução para este problema.

Exercício 2

Encontre a melhor solução para o problema de localização de um novo depósito para abastecer todos os supermecardos, no qual os supemercados são pontos com duas coordenadas (x,y).
 
http://br.spoj.pl/problems/SUPERMER/

O novo depósito deve ficar localizado na (mediana dos valores da coordenadas de x, na mediana dos valores de y).

 Teste

 

Solução 1391894 class vector + sort (algoritm)

Solução 2702601 qsort

Solução 3956537 usando selection não randômico

Solução 3956542 usando selection randômico