Encontrar mediana de matriz não triados em

Para encontrar a mediana de uma matriz não classificada, podemos fazer um min-heap em para elementos e, em seguida, podemos extrair um por um elementos para obter a mediana. Mas essa abordagem levaria tempo . $O(n\log n)$ $n$ $n/2$ $O(n \log n)$

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

algorithms time-complexity Luv
fonte

en.wikipedia.org/wiki/Selection_algorithm

Jukka Suomela

@JukkaSuomela Por que não fazer desta uma resposta rápida e simples (com uma breve explicação de um desses algoritmos, idealmente)?

Raphael

Observe a meta discussão relacionada ; Acontece que pesquisas simples na web levam à resposta a essa pergunta.

Raphael

stackoverflow.com/questions/2571358/median-of-a-billion-numbers

Evgeny

Respostas:

Este é um caso especial de um algoritmo de seleção que pode encontrar o menor elemento de uma matriz com é a metade do tamanho da matriz. Existe uma implementação que é linear no pior dos casos. $k$ $k$

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(n^2)$

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

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

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

octavian

$n^{-1/4}$ $O(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