Analisando o pior caso a complexidade de tempo de classificação rápida em diferentes casos

Question

Eu estou tentando entender a pior complexidade do tempo de Classe de Quick para vários pivôs. Aqui é o que eu me deparei:

.

1. quando a matriz já está classificada em ordem ascendente ou ordem decrescente e selecionamos o elemento mais à esquerda ou mais à direita como pivô, então resulta em pior caso $ O (n ^ 2) $ complexidade de tempo.

2. quando a matriz ainda não está classificada e selecionamos elemento aleatório como pivô, então ele dá pior caso "esperado" a complexidade de tempo como $ O (n \ log n) $ . Mas a pior complexidade do tempo ainda é $ O (n ^ 2) $ . ^[1]

3. Quando selecionar mediana de ^{[2] primeiro, último e médio elemento como pivô, então resulta em pior caso a complexidade do tempo da $ O (n \ log n) $ [1]}

Eu tenho seguindo dúvidas

d1. link [2] diz, se todos os elementos na matriz são os mesmos, tanto o pivô aleatório quanto o pivô mediano levarão à $ O (n ^ 2) $ complexidade de tempo. No entanto link [1] diz que media pivô produz $ O (n \ log n) $ Pior complexidade do tempo de caso. O que é correto?

d2. Como a mediana do primeiro, último e médio elemento pode ser mediana de todos os elementos?

d3. O que fazemos quando o pivô aleatório é $ i $ th elemento? Nós sempre temos que trocá-lo com o elemento mais à esquerda ou mais à direita antes de particionar? Ou há algum algoritmo que não exija tal troca?

Answer 1

Não há nenhum quicksort.Há um original, que só nos importamos por razões históricas, e muitas variações, todas diferentes.

No caso de n Itens idênticos, diferentes implementações serão executadas em O (n Log n) ou O (n ^ 2).Como isso é um caso prático, o último tipo de algoritmo deve ser evitado.

Seu ponto (3) está errado.Pior caso para n itens diferentes é sempre O (n ^ 2).No caso (2) não importa se a matriz já estiver classificada.

Tomando um elemento aleatório como a mediana garante que um adversário não possa criar uma matriz que leva n ^ 2 etapas para classificar.Mediana de três elementos aleatórios geralmente dividirá melhor a matriz e, portanto, será mais rápida.

Mas, além do caso de tomar o primeiro ou último elemento com uma matriz classificada, e problemas com todos ou muitos itens idênticos, o mau comportamento não acontecerá a menos que você tenha um invasor que possa criar os dados a serem classificados, oucom má sorte extraordinariamente.

Answer 2

A regra usual aqui é apenas uma pergunta por post.

link [2] não diz que pivô aleatório e pivô mediano levam a $ O (n ^ 2) $ complexidade de tempo.

A mediana do primeiro, médio e último elemento não é a mediana de toda a matriz.Escrevendo "mediana pivô" é provavelmente uma má ideia, a menos que você tenha especificado cuidadosamente o que é uma mediana de.

Link [1] diz que levando a mediana de todos os elementos leva a $ o (n \ log n) $ complexidade de tempo.Isso é diferente de tomar a mediana de primeiro, meio e por último.Além disso, é raro que as implementações práticas tenham a mediana de todos os elementos, já que esse link já declara.