Indo além do óbvio: mediana de um array
Achar a mediana de um array é um problema clássico de algoritmos. E não é clássico a toa: é um problema simples de entender, possui diversas formas de resolver e cada uma com seus respectivos trade-offs. As soluções são amplamente discutidas em livros como Algoritmos Teoria e Prática e nesse post vamos discutir as principais.
O que é mediana?
Recorro ao livro Estatística Básica para obter uma definição formal.
Mediana é o valor que ocupa a posição central de uma série de números, quando estão ordenados em ordem crescente.
Dado essa definição é fácil achar a mediana do array abaixo:
array: [2, 5, 5, 12, 45, 100, 456]mediana: 12
Achar a mediana de um array já ordenado não oferece desafios. Porém, como achar a mediana de um array que não está ordenado?
1. Solução: Ordenar o array
A solução óbvia de ser implementada para esse problema é ordenar o array e obter o elemento do meio. Convido você a fazer a seguinte reflexão: “precisamos organizar todos os elementos quando queremos apenas achar um elemento específico?”
Se os arrays possuem poucos elementos (10, 100) talvez você não note nenhuma demora na ordenação, no entanto, a medida que trabalhamos com arrays maiores (1k, 10k, 100k) é notável a diferença no desempenho, isso porque a complexidade assintótica dominante é a da ordenação, que é O(nlogn).
Reflexão: Por que sempre pensamos em ordenar o array?
Um dos grandes motivos que nos leva a pensar em ordenar o array é que a definição nos induz a implementar dessa forma. Abaixo, novamente, a definição:
Mediana é o valor que ocupa a posição central de uma série de números, quando estão ordenados em ordem crescente.
Note que a própria definição nos induz a pensar que ordenação é o caminho óbvio. O que é excelente para uma definição, pois é objetiva, fácil de memorizar, intuitiva e fácil de explicar para outras pessoas. Mesmo assim, na hora de implementarmos um algoritmo, devemos sempre nos questionar se não há uma forma melhor de resolver o problema.
2. Solução: seleção ingênua
Uma definição equivalente é adotarmos que a mediana é o i-ésimo menor valor do array. Considere o array abaixo com os mesmos elementos do exemplo acima, porém desordenado:
array: [12, 5, 100, 456, 5, 45, 2]O array acima possui 7 elementos e a mediana é o 4° menor valor do array:
array: [12, 5, 100, 456, 5, 45, 2]1° menor: 2
2° menor: 5
3° menor: 5
4° menor: 12
Uma possível implementação é obter o menor valor do dado array e removê-lo do array. Como sabemos de antemão o tamanho do array (no caso 7), repetimos esse processo 4 vezes para pegarmos o 4° menor valor, que é a mediana 12.
Apesar de simples, essa implementação ainda é ingênua e ineficiente para arrays com muitos elementos. Se um dado array possui tamanho N, temos que repetir esse processo N/2 vezes sendo que a cada iteração, removemos apenas 1 elemento. Em resumo, a complexidade assintótica dessa solução é O(n²) que é pior que o da solução de ordenar o array.
3. Solução: divisão e conquista
Outra forma interessante de acharmos a mediana de um array é usando divisão e conquista. A melhor forma de entender como funciona esse algoritmo é através de exemplos. Para isso, considere o seguinte array desordenado de tamanho 15:
array: [3,2,4,15,5,9,1,15,8,10,0,11,7,6,13]Agora divida o dado array em grupos de 5 elementos:
array: [3,2,4,15,5,9,1,15,8,10,0,11,7,6,13]divididos: [3,2,4,15,5] [9,1,15,8,10] [0,11,7,6,13]
O objetivo é obter as medianas dos 3 arrays individualmente. Para isso, podemos ordenar cada um deles. O resultado é:
array: [3,2,4,15,5,9,1,15,8,10,0,11,7,6,13]divididos: [3,2,4,15,5] [9,1,15,8,10] [0,11,7,6,13]ordenados: [2,3,4,5,15] [1,8,9,10,15] [0,6,7,11,13]
Para ordenar cada array usamos o algoritmo de ordenação por inserção, que possui complexidade O(n²) no pior caso porém O(n) no melhor caso. Essa ordenação é ideal para arrays com poucos elementos, por isso dividimos em grupos de 5.
Nessa abordagem cada array de 5 elementos precisará de 25 comparações (no pior caso), custando O(25), equivalente a O(1). Logo, para ordenar vários arrays de tamanho 5, a complexidade assintótica é O(N).
E com isso é fácil obter a mediana de cada array apenas consultando o elemento do meio de cada array:
array: [3,2,4,15,5,9,1,15,8,10,0,11,7,6,13]divididos: [3,2,4,15,5] [9,1,15,8,10] [0,11,7,6,13]ordenados: [2,3,4,5,15] [1,8,9,10,15] [0,6,7,11,13]medianas: [4,9,7]
Fazendo isso recursivamente no array de medianas, é possível achar a mediana das medianas que é 7.
Conclusão
Achar a mediana é um problema clássico por ser fácil de entender, porém, suas implementações possuem um trade-off entre simplicidade e complexidade. Problemas assim são amplamente discutidos em salas de aulas por serem ricos em teoria da computação e, atualmente, são explorados também em entrevistas de empresas de tecnologia pelos mesmos motivos.
O objetivo desse post não é discutir os detalhes de implementação em si mas trazer a reflexão de como pensar em solucionar um problema. Por exemplo, foi fácil pensarmos na ordenação porque a definição nos induzia a pensar assim. No entanto, quando interpretamos o problema de outra maneira (procurar o i-ésimo menor), passamos a cogitar outras formas de resolvê-lo.
Agradeço ao @apolotakeshi pela sugestão! Brigado meu brother!
