Existem algoritmos ou estruturas de dados que precisam encontrar o valor mediano de um conjunto?

Eu tenho lido este livro para minha turma, Algoritmos Aleatórios. Neste livro em particular, há uma seção inteira dedicada a encontrar a mediana de uma matriz usando seleção aleatória, que leva a um algoritmo mais eficiente. Agora, eu queria saber se existem aplicações práticas desse algoritmo, no domínio da ciência da computação, além de uma melhoria teórica. Existem algoritmos ou estruturas de dados que precisam encontrar a mediana de uma matriz?

se existe alguma aplicação prática desse algoritmo no domínio da ciência da computação, além de ser uma melhoria teórica

A aplicação desse algoritmo é trivial - você o utiliza sempre que quiser calcular uma mediana de um conjunto de dados (array em outras palavras). Esses dados podem vir de diferentes domínios: observações astronômicas, ciências sociais, dados biológicos, etc.

No entanto, vale mencionar quando preferir mediana à média (ou modo). Basicamente, nas estatísticas descritivas, quando nossos dados são perfeitamente normais distribuídos, a média, o modo e a mediana são iguais, ou seja, coincidem. Por outro lado, quando nossos dados são distorcidos, ou seja, a distribuição de frequência de nossos dados é distorcida (esquerda / direita), a média falha em fornecer a melhor localização central, porque a distorção os afasta do valor típico para a esquerda ou direita. , enquanto a mediana não é tão fortemente influenciada pelos dados distorcidos e, portanto, mantém melhor essa posição apontando para um valor típico. Assim, calcular uma mediana pode ser preferível quando você lida com dados distorcidos.

Além disso, o aprendizado de máquina é onde os métodos estatísticos são muito usados, por exemplo, medians clustering .$k$

A filtragem mediana é comum na redução de certos tipos de ruído no processamento de imagens. Especialmente barulho de sal e pimenta. Ele funciona escolhendo o valor mediano em cada canal de cores em cada vizinhança local da imagem e substituindo-o por ele. O tamanho desses bairros pode variar. Os tamanhos de filtro populares (vizinhanças) são, por exemplo, 3x3 e 5x5 pixels.

A mediana da computação é particularmente importante em algoritmos aleatórios.

$\tfrac34$$1\pm\epsilon$$A$$\tfrac34$$k$$A(1\pm\epsilon)$$k$$A(1-\epsilon)$$A(1+\epsilon)$$k$

$2^n$$n$

A mediana de medianas tem algumas aplicações:

• $O(n \log n)$
• $O(n)$$O(n^2)$