Encontrar mediana de matriz não triados em

45

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)nn/2O(nlogn)

Podemos fazer o mesmo por algum método em time? Se pudermos, então como?O(n)

Luv
fonte
11
@JukkaSuomela Por que não fazer desta uma resposta rápida e simples (com uma breve explicação de um desses algoritmos, idealmente)?
Raphael
2
Observe a meta discussão relacionada ; Acontece que pesquisas simples na web levam à resposta a essa pergunta.
Raphael

Respostas:

45

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.kk

Algoritmo de seleção genérico

Primeiro vamos ver um algoritmo find-kthque encontra o menor elemento de uma matriz:k

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

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.

O(n)O(n2)

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.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

O(n)

Observe que na maioria das vezes o uso de um pivô aleatório é mais rápido.

jmad
fonte
Esse tamanho é 5padrão? E se o tamanho de A for menor que 5?
Jayesh
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).
v6ak
3
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.
Wcochran
2
@NickCaplinger corrigido usando web.archive.org
jmad 17/05
11
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.
octavian
6

n1/4O(n)

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.

zdm
fonte