Mediana de medianas

Mediana de medianas

Descobridores ou inventores	Manuel Blum , Robert Floyd , Vaughan Pratt ( en ) , Ronald Rivest , Robert Tarjan
Data da descoberta	1972
Problema relacionado	Algoritmo de seleção
Estrutura de dados	Borda
Baseado em	Seleção rápida

Complexidade de tempo

Pior caso	O(não){\ displaystyle O (n)}
Melhor caso	O(não){\ displaystyle O (n)}

Complexidade do espaço

Pior caso	O(registro⁡não){\ displaystyle O (\ log n)}

A mediana das medianas é um algoritmo de seleção para encontrar o k- ésimo maior elemento em uma lista não classificada. É baseado no algoritmo Quickselect . Este algoritmo é ótimo no pior caso , com complexidade no tempo linear. O bloco de construção básico do algoritmo é a seleção de uma mediana aproximada no tempo linear. O algoritmo é às vezes chamado de BFPRT após os nomes dos autores: Blum , Floyd , Pratt  (in) , Rivest e Tarjan .

Princípio geral do algoritmo

O algoritmo ocorre em 3 etapas:

• O algoritmo divide a lista em grupos de cinco elementos. Então, para cada grupo de cinco, a mediana é calculada (uma operação que pode ser feita em tempo constante, por exemplo, usando um algoritmo de classificação ).
• O algoritmo é então chamado recursivamente nesta sublista de elementos para encontrar a verdadeira mediana desses elementos. Pode-se então garantir que o item obtido se situa entre o 30º e o 70º percentis .não/5{\ displaystyle n / 5}
• Finalmente, a mediana das medianas é escolhida para ser o pivô. Dependendo da posição do elemento buscado, o algoritmo recomeça com os elementos acima ou abaixo do pivô, que representam no máximo 70% do tamanho inicial do espaço de busca.

Propriedades de pivô

Entre os grupos, metade tem sua mediana abaixo do pivô (a mediana das medianas), o que garante pelo menos itens abaixo do pivô (3 em cada um dos grupos). Assim, o pivô escolhido é menor do que sobre os elementos e maior do que os elementos. Assim, a mediana divide os elementos escolhidos em algum lugar entre 30% ⁄ 70% e 70% ⁄ 30% , o que garante no pior caso um comportamento linear do algoritmo. Ver: não/5{\ displaystyle n / 5}3não/10{\ displaystyle 3n / 10}não/10{\ displaystyle n / 10}3não/10{\ displaystyle 3n / 10}3não/10{\ displaystyle 3n / 10}

Uma iteração das duas primeiras etapas do algoritmo em {0,1,2,3, ... 99}

	12		15		11		2		9		5		0		7		3		21		44		40		1		18		20		32		19		35		37		39
	13		16		14		8		10		26		6		33		4		27		49		46		52		25		51		34		43		56		72		79
Medianas	17		23		24		28		29		30		31		36		42		47		50		55		58		60		63		65		66		67		81		83
	22		45		38		53		61		41		62		82		54		48		59		57		71		78		64		80		70		76		85		87
	96		95		94		86		89		69		68		97		73		92		74		88		99		84		75		90		77		93		98		91

Em vermelho, a mediana das medianas.

Prova de O (n)

Com o tempo de execução do algoritmo em uma entrada de tamanho , temos a seguinte recorrência: T(não){\ displaystyle T (n)}não{\ displaystyle n}

T(não)≤T(não/5)+T(7não/10)+vs⋅não{\ displaystyle T (n) \ leq T (n / 5) + T (7n / 10) + c \ cdot n}

ou

• o fator é a busca da mediana entre as medianas quíntuplas.T(não/5){\ displaystyle T (n / 5)}não/5{\ displaystyle n / 5}
• o fator é o custo do trabalho de particionamento em torno do pivô.vs⋅não{\ displaystyle c \ cdot n}
• o fator é a chamada recursiva (no pior caso) para encontrar o k - ésimo elemento na partição correspondente.T(7não/10){\ displaystyle T (7n / 10)}

A partir desta fórmula de recorrência, simplesmente verificamos por indução:

T(não)≤10⋅vs⋅não∈O(não).{\ displaystyle T (n) \ leq 10 \ cdot c \ cdot n \ in O (n).}

Outros usos da mediana

A seleção de uma mediana aproximada em tempo linear também pode ser usada para garantir a complexidade de classificação rápida no pior caso. Em ambos os casos, o uso da mediana é em média menos eficiente do que a escolha de um pivô aleatório, o que evita o custo adicional de cálculo do pivô. O(nãoregistro⁡não){\ displaystyle O (n \ log n)}

História

O algoritmo da mediana das medianas foi publicado por Blum , Floyd , Pratt  (in) , Rivest e Tarjan em 1973 em Limites de tempo para seleção e às vezes é chamado de BFPRT após os nomes dos autores.

Veja também

• (fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado "  Algoritmo de seleção  " ( ver a lista de autores ) .

Notas e referências

1. (em) Manuel Blum , Robert W. Floyd , Vaughan Pratt, Ronald L. Rivest e Robert E. Tarjan , "  Time bounds for selection  " , Journal of Computer and System Sciences , Elsevier , vol.  7, n o  4,Agosto de 1973, p.  448-461 ( ISSN  0022-0000 e 1090-2724 , DOI  10.1016 / S0022-0000 (73) 80033-9 )
2. (em) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein , Introdução a Algoritmos , MIT Press ,2009, 3 e  ed. [ detalhe da edição ]
3. (em) Blum, RW Floyd, V. Pratt, R. e R. Rivest Tarjan , "  Time bounds for selection  " , J. Comput. System Sci. , vol.  7,1973, p.  448-461