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

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 como$O(n^2)$$O(n\log{n})$

O que é correto?

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(n \log n).$

O Quicksort geralmente possui um requisito de tempo absoluto no pior dos casos de $O(n^2)$ . 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$n$$1$$n-1$$O(n)$$O(n^2)$

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(n\log n)$

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)$$\Theta(n \log n)$ 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.

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.

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$$\Theta(n \log n)$

$\Theta(n \log n)$

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

$O(n^2)$

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

$T(n) = T(n-1) + n$$O(n^2)$