Para encontrar a mediana de uma matriz não classificada, podemos fazer um min-heap em para n elementos e, em seguida, podemos extrair um por um n / 2 elementos para obter a mediana. Mas essa abordagem levaria tempo O ( n log n ) .O(nlogn)O(nlog⁡n)nnn/2n/2O(nlogn)O(nlog⁡n)
Podemos fazer o mesmo por algum método em time? Se pudermos, então como?O(n)O(n)
@JukkaSuomela Por que não fazer desta uma resposta rápida e simples (com uma breve explicação de um desses algoritmos, idealmente)?
Observe a meta discussão relacionada ; Acontece que pesquisas simples na web levam à resposta a essa pergunta.
Este é um caso especial de um algoritmo de seleção que pode encontrar o menor elemento de uma matriz com k é a metade do tamanho da matriz. Existe uma implementação que é linear no pior dos casos.kkkk
Algoritmo de seleção genérico
Primeiro vamos ver um algoritmo find-kthque encontra o menor elemento de uma matriz:kk
A função split(A, pivot)retorna de L,Rforma que todos os elementos em Rsejam maiores que pivote Ltodos os outros (menos uma ocorrência de pivot). Então tudo é feito recursivamente.
Pior caso linear: o algoritmo de mediana de medianas
Um pivô melhor é a mediana de todas as medianas de sub-matrizes Ade tamanho 5, usando a chamada do procedimento na matriz dessas medianas.
Observe que na maioria das vezes o uso de um pivô aleatório é mais rápido.
Esse tamanho é 5padrão? E se o tamanho de A for menor que 5?
Para qualquer n fixo, a complexidade é constante, a menos que seja infinita. Portanto, você pode usar qualquer algoritmo válido com complexidade finita para esse caso especial, mesmo que fosse O (2 ^ n). Para um n fixo (ou seja, no máximo 4 no caso externo), a complexidade é no máximo O (2 ^ 4) = O (1).
No primeiro algoritmo: return A[k]está incorreto (a menos que Aseja classificado, o que tornaria o algoritmo discutível). Se splitaconteceu de se dividir de Atal forma que k = |L| + 1você ainda não sabe onde está o kelemento th. Seu caso base é quando |A| = 1mais você ainda precisa fazer uma das duas chamadas recursivas.
@NickCaplinger corrigido usando web.archive.org
— jmad 17/05
Não é o pior caso para o algoritmo de seleção genérico O (NlogN)? Mesmo se as folhas chamada recursiva apenas 10% da matriz após cada chamada, em seguida, ainda é um logaritmo na base 10.
A idéia principal do algoritmo é usar amostragem. Temos que encontrar dois elementos que estão próximos na ordem classificada da matriz e que possuem a mediana entre eles. Veja a referência [MU2017] para uma discussão completa.
[MU2017] Michael Mitzenmacher e Eli Upfal. "Probabilidade e computação: aleatorização e técnicas probabilísticas em algoritmos e análise de dados", capítulo 3, páginas 57-62. Cambridge University Press, segunda edição, 2017.