Por que o Randomized Quicksort tem O (n log n) no pior caso, custo de tempo de execução

18

A Classificação Rápida Aleatória é uma extensão da Classificação Rápida, na qual o elemento dinâmico é escolhido aleatoriamente. Qual pode ser a pior complexidade de tempo desse caso? De acordo com mim, deve ser , como o pior caso ocorre quando o pivô escolhido aleatoriamente é selecionado na ordem classificada ou na ordem inversa . Mas em alguns textos [1] [2], a pior complexidade do tempo é escrita comoO(n2)O(nlogn)

O que é correto?

Atinesh
fonte
3
Você deve este "algum texto" que você está falando. Há algo escondido lá. Você o encontrará se ler novamente este "texto"
AJed
Nota: O link [1] está morto. Link [2] afirma claramente que o algoritmo é randomizado, portanto, para qualquer entrada, você não possui "um tempo de execução", mas "um tempo de execução esperado". E o tempo de execução esperado para a pior entrada possível é O (n log n).
gnasher729

Respostas:

18

As duas fontes se referem ao "pior caso de tempo de execução esperado" deAcho que isso se refere ao requisito de tempo esperado, que difere do pior caso absoluto.O(nlogn).

O Quicksort geralmente possui um requisito de tempo absoluto no pior dos casos de O(n2) . O pior caso ocorre quando, a cada etapa, o procedimento de partição divide uma matriz de comprimento em matrizes de tamanho e . Essa seleção "infeliz" de elementos dinâmicos requer chamadas recursivas, levando ao pior caso de .1 n - 1 O ( n ) O ( n 2 )n1n1O(n)O(n2)

Escolher o pivô aleatoriamente ou aleatoriamente a matriz antes da classificação tem o efeito de tornar o pior caso muito improvável, principalmente para matrizes grandes. Consulte a Wikipedia para obter uma prova de que o requisito de tempo esperado é . De acordo com outra fonte , "a probabilidade de o quicksort usar um número quadrático de comparações ao classificar uma grande matriz no seu computador é muito menor que a probabilidade de o computador ser atingido por um raio".O(nlogn)

Editar:

De acordo com o comentário de Bangye, você pode eliminar a pior sequência de seleção de pivô selecionando sempre o elemento mediano como o pivô. Como encontrar a mediana leva tempo , isso forneceΘ ( n log n )O(n)Θ(nlogn) pior caso. No entanto, como é muito improvável que o quicksort aleatório encontre o pior caso, a variante determinística da descoberta mediana do quicksort raramente é usada.

James Evans
fonte
Assim, em geral, podemos dizer que se comporta como quadrática no pior caso
Atinesh
@Atinesh Não, pelo menos, se você quer dizer por isso. Θ
Raphael
Eu acho correto dizer que o pior desempenho do quicksort aleatório é O(n2).
James Evans
4
Θ(nlogn)
6

Você estava sentindo falta desses textos falar sobre "pior caso de tempo de execução esperado ", não "pior caso de execução".

Eles estão discutindo uma implementação do Quicksort que envolve um elemento aleatório. Normalmente você tem um algoritmo determinístico, que é um algoritmo que, para uma determinada entrada, sempre produzirá exatamente as mesmas etapas. Para determinar o "pior caso de execução", examine todas as entradas possíveis e escolha a que produz o pior tempo de execução.

Mas aqui temos um fator aleatório. Dada alguma entrada, o algoritmo nem sempre executa as mesmas etapas porque está envolvida alguma aleatoriedade. Em vez de ter um tempo de execução para cada entrada fixa, temos um "tempo de execução esperado" - verificamos cada valor possível das decisões aleatórias e sua probabilidade, e o "tempo de execução esperado" é a média ponderada do tempo de execução para cada combinação de decisões aleatórias , mas ainda para uma entrada fixa.

Portanto, calculamos o "tempo de execução esperado" para cada entrada possível e, para obter o "pior tempo de execução esperado", encontramos a única entrada possível em que o tempo de execução esperado é pior. E, aparentemente, eles mostraram que o pior caso para o "tempo de execução esperado" é apenas O (n log n). Eu não ficaria surpreso se apenas escolher o primeiro pivô aleatoriamente alterasse o pior caso de execução esperado para o (n ^ 2) (pouco o em vez de Big O), porque apenas alguns dos n pivôs levarão ao pior caso comportamento.

gnasher729
fonte
2

Observe que há duas coisas a serem superadas pelas expectativas / média: a permutação de entrada e os pivôs (um por particionamento).

nΘ(nlogn)

Θ(nlogn)

Bottom line, verifique suas fontes para qual implementação eles usam e qual quantidade eles consideram aleatório resp. fixado em sua análise.

Rafael
fonte
Considere esta pergunta postimg.org/image/fiurc4z87 que eu fiz no exame. Que ans apropriado você sugeriria que eu ache (c)
Atinesh
1
@ Atinesh Acho que minha resposta fornece informações suficientes sobre isso.
Raphael
-1

O(n2)

O pior caso para o quicksort aleatório é o mesmo elemento que a entrada. Ex: 2,2,2,2,2,2

T(n)=T(n1)+nO(n2)

pratyay
fonte
Isso se você tiver uma implementação extremamente rápida do quicksort. Qualquer implementação decente na primeira troca partição # 1 e # 6, # 2 e # 5, # 3 e # 4, e será, em seguida, tipo duas subarrays de comprimento 3.
gnasher729
Eu acho que você tem <= assim como> = nos dois ponteiros que varre a partir do LHS e RHS. É por isso que você está dizendo isso. '=' está associado a qualquer um dos ponteiros, não a ambos. Nesse caso, a árvore de recursão cresce até n.
Pratyay
E é isso que chamo de implementação extremamente tola. Qualquer implementação que leva tempo de execução quadrático para o caso "todos os elementos são iguais" é criminalmente estúpida. Na verdade, existem implementações que levam tempo linear neste caso (O (n), não O (n log n)).
gnasher729