Melhor e pior caso de entrada para classificação de heap e classificação rápida?

heap- Uma vez que o melhor e o pior caso são iguais não importa a ordem de entrada? O número de comparações e atribuições será sempre o mesmo? Imagino que em uma classificação de heap possa ser o mesmo, já que o trabalho real é feito na inserção, mas a classificação usa apenas a remoção do heap máximo / mínimo? É por isso?

O número de comparações feitas realmente pode depender de a ordem em que os valores são fornecidos. O fato de que o melhor e o pior caso são Θ (n log n) – assumindo que todos os elementos são distintos – significa apenas que assintoticamente não há diferença entre os dois, embora possam diferir por um fator constante. Não tenho nenhum exemplo simples disso na minha cabeça, mas acredito que você pode construir entradas onde o número de comparações difere por um fator constante entre os duas abordagens. Porém, como a notação big-O ignora constantes, isso não se reflete na análise do melhor e do pior caso.

classificação rápida- Este aqui Não sei ao certo. Não tenho certeza de quais são as situações de melhor e pior caso para isso. Se for uma lista já classificada de 10 strings, por exemplo, não teríamos sempre que escolher a mesma quantidade de pivôs para completar o algoritmo recursivo? Qualquer ajuda nesta explicação ajudaria muito.

O número de pivôs escolhidos é realmente o mesmo, independentemente da execução do algoritmo. No entanto, o trabalho realizado por pivô pode variar com base no tipo de divisões que você obtém. Na melhor das hipóteses, o pivô escolhido em cada etapa acaba sendo o elemento mediano do array. Quando isso acontece, existem (aproximadamente) n comparações feitas na camada superior da recursão, então (aproximadamente) n na próxima camada porque existem dois submatrizes de tamanho n / 2, então existem (aproximadamente) n no próximo camada porque existem quatro submatrizes de tamanho n / 4, etc. Uma vez que existem Θ (log n) camadas e cada camada tem Θ (n) trabalho, o trabalho total realizado é Θ (n log n). Por outro lado, considere escolher o mínimo absoluto de cada matriz como um pivô. Então (aproximadamente) n comparações são feitas na camada superior, então (aproximadamente) n – 1 na próxima camada, então (aproximadamente) n – 2 na próxima, etc. A soma 1 + 2 + 3 + … + n é Θ (n ² ), portanto, o pior caso.

Espero que ajude!

Comentários

• Senhor, como é o melhor caso de heapsort nlogn? Se considerarmos que todos os elementos são idênticos, o custo seria apenas iterar por todos os elementos da matriz e não subir até a raiz. Portanto, deve ser ômega (n) para mim.
• Esse é um bom ponto. Eu estava assumindo elementos distintos, então irei atualizar esta resposta.

Já que ninguém está realmente abordou heapSort ainda:

Supondo que você “esteja usando um heap máximo representado como uma matriz e inserindo seus elementos máximos para trás em sua matriz de saída / na parte de trás de sua matriz, se estiver fazendo isso no local , o pior caso de entrada para heapSort é qualquer entrada que força você a “bolha para baixo” ou reaparecer toda vez que você remove um elemento. Isso acontece toda vez que você está tentando classificar um conjunto sem duplicatas. Ainda será Θ (n log n), como templatetypedef disse.

Esta propriedade implica que o melhor caso de heapSort é quando todos os elementos são iguais (Θ (n), uma vez que você não precisa reaparecer após cada remoção, o que leva tempo log (n) desde o a altura máxima da pilha é log (n)). No entanto, é um caso ruim / pouco prático, por isso o melhor caso real para o heapsort é Θ (n log n).

Comentários

• Seu ponto de vista sobre o caso pouco prático acabou de ser perguntado na minha aula de algoritmos. (cuidado com as perguntas capciosas.) Claro, eu ‘ ainda estou de acordo com seu ponto de vista. ( e obtive minha resposta errada como resultado XD)

• Classificação rápida

  Pior caso: $ \ mathcal {O} (n ^ 2) $ . Vamos supor que o elemento pivô é sempre o elemento mais à direita: insira um já lista classificada com elementos $ n $ . Assim, cada particionamento leva a uma lista com elementos $ n-1 $ e uma lista com elementos $ 0 $ . Mesmo se você escolher o elemento dinâmico aleatoriamente , você ainda pode ter azar e sempre escolher o valor máximo na lista.

  Seja $ T (n) $ o número de comparações quicksort requer a classificação de uma lista com elementos $ n $ . Pior caso: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ recursivo, $ n $ para partição)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Melhor caso: $ \ mathcal {O} (n \ log n) $ . Se o elemento pivô for escolhido de forma que particione a lista de maneira uniforme:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 vezes $ \ frac {n} { 2} $ recursivo, $ n $ para particionar)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {teorema mestre}) \ end {align}

• Classificação de heap

  O pior caso e o melhor caso de complexidade para classificação de heap são $ \ mathcal {O} (n \ log n) $ . Portanto, a classificação de heap precisa de $ \ mathcal {O} (n \ log n) $ comparações para qualquer array de entrada. Complexidade da classificação de heap:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ texto {regra de quociente logarítmico}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ direita) \ end {alinhar }

Comentários

• Você não ‘ t respondi a todas as perguntas do OP ‘ s, então responderei uma que você perdeu; a classificação de heap não ‘ sempre usa o mesmo número de comparações para um determinado número de elementos. O pior caso é $ a \, n \ log n $ e o melhor caso é $ b \, n \ log n $, onde $ a > b $.
• Observe também que a variante de três vias tem o melhor caso linear para entrada de elemento único.