Nítida concentração para seleção via particionamento aleatório?

O algoritmo simples usual para encontrar o elemento mediano em uma matriz de números é: $A$ $n$

Amostra de elementos de com substituição em $n^{3/4}$ $A$ $B$
Ordenar $B$ e encontrar o posto $|B|\pm \sqrt{n}$ elementos $l$ e $r$ de $B$
Verifique se $l$ e $r$ estão em lados opostos da mediana de $A$ e se existem no máximo $C\sqrt{n}$ elementos em $A$ entre $l$ e $r$ para alguma constante constante $C > 0$ . Falha se isso não acontecer.
Caso contrário, encontre a mediana classificando os elementos de $A$ entre $l$ e $r$

Não é difícil ver que isso ocorre em tempo linear e que é bem-sucedido com alta probabilidade. (Todos os eventos ruins são grandes desvios da expectativa de um binômio.)

Um algoritmo alternativo para o mesmo problema, que é mais natural para ensinar aos alunos que viram uma classificação rápida, é o descrito aqui: Seleção Aleatória

Também é fácil ver que este possui um tempo de execução linear esperado: digamos que um "round" seja uma sequência de chamadas recursivas que termina quando se faz uma divisão 1 / 4-3 / 4 e, em seguida, observe que a duração esperada de uma rodada é no máximo 2. (No primeiro sorteio de uma rodada, a probabilidade de obter uma boa divisão é 1/2 e depois depois aumenta de fato, pois o algoritmo foi descrito para que o comprimento da rodada seja dominado por uma variável geométrica aleatória.)

Então agora a pergunta:

É possível mostrar que a seleção aleatória é executada em tempo linear com alta probabilidade?

Temos rodadas, e cada rodada tem comprimento pelo menos com probabilidade no máximo , portanto, um limite de união indica que o tempo de execução é com probabilidade . $O(\log n)$ $k$ $2^{-k+1}$ $O(n\log\log n)$ $1-1/O(\log n)$

Isso é meio insatisfatório, mas é realmente a verdade?

algorithms algorithm-analysis randomized-algorithms Louis
fonte

Esclareça a qual algoritmo suas perguntas se referem.

Raphael

Você está perguntando se aplicou corretamente seu vínculo de união ou se existe um vínculo melhor e mais satisfatório?

18712 Joe

@ Joe O último. O ponto é que as rodadas são um artefato para conseguir que o comprimento da rodada seja dominado por uma geométrica. Então o anaylisys "esquece" se o algoritmo está à frente ou atrás do que sempre recebe uma divisão de 1 / 4-3 / 4 no nariz para tornar a geometria independente. Estou perguntando se essa "trapaça", como Yuval colocou abaixo, ainda é forte.

Louis

Respostas:

$\Theta(n)$ $G(1/2)$ $p(n) \longrightarrow 0$ $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$ $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$

(Há alguma trapaça envolvida, pois a duração do primeiro turno não é realmente . Uma análise mais cuidadosa pode ou não validar essa resposta.) $G(1/2)$

Edit: Grübel e Rosler provaram que o número esperado de comparações divididas por tende (em certo sentido) a alguma distribuição limite, que é ilimitada. Veja, por exemplo, o artigo de Grübel "O algoritmo de seleção de Hoare: uma abordagem de cadeia de Markov", que faz referência ao artigo original. $n$

Yuval Filmus
fonte

Aqui está a coisa que me incomoda. Como eu disse no meu comentário acima, as rodadas são apenas uma maneira de analisar uma versão "mais lenta" do algoritmo que espera até que ele tenha um pivô suficientemente bom para prosseguir. O que você está mostrando é que, para qualquer fixo, a probabilidade do primeiro turno precisar de mais de pivôs é . Mas, em princípio, uma longa primeira rodada pode ser compensada por uma 2ª rodada vazia, no sentido de que, no final, o algoritmo "não abrandado" alcançou o que sempre recebe uma divisão de 1 / 4-3 / 4 .

C > 0

$C>0$

C

$C$

> 0

$>0$

Louis

C

$C$

C n

$Cn$

p_{C} > 0

$p_C > 0$

Estou mais feliz agora, já que o comprimento da ronda não é muito menor que o geométrico usado para o limite superior. Eu acho que isso é o que a G&R está fazendo com que seja violento. Boa resposta.

Louis