Les meilleures et pires entrées de cas pour le tri en tas et le tri rapide?

tas- Puisque le meilleur et le pire des cas sont les mêmes peu importe lordre dentrée? Le nombre de comparaisons et daffectations sera toujours le même? Jimagine que dans un tri de tas, il peut en être de même puisque le vrai travail est effectué dans linsertion, mais le tri utilise uniquement la suppression du tas max / min? Est-ce pourquoi?

Le nombre de comparaisons effectuées peut dépendre de lordre dans lequel les valeurs sont données. Le fait que le meilleur et le pire des cas soient chacun Θ (n log n) – en supposant que tous les éléments sont distincts – signifie seulement que asymptotiquement il ny a pas de différence entre les deux, même si elles peuvent différer par un facteur constant. Je n « ai pas d » exemples simples de cela par tête, mais je crois que vous pouvez construire des entrées où le nombre de comparaisons diffère par un facteur constant entre le deux approches. Puisque la notation big-O ignore les constantes, cependant, cela ne se reflète pas dans lanalyse du meilleur et du pire des cas.

tri rapide – Celui-ci Je ne sais pas avec certitude. Je ne sais pas quel est le meilleur des cas et les pires situations pour cela. Si cest une liste déjà triée de 10 chaînes par exemple, nous naurions pas toujours à choisir le même nombre de pivots pour terminer lalgorithme récursif? Toute aide sur cette explication serait vraiment utile.

Le nombre de pivots choisis est en effet le même quelle que soit lexécution de lalgorithme. Cependant, le travail effectué par pivot peut varier en fonction du type de fractionnement obtenu. Dans le meilleur des cas, le pivot choisi à chaque étape finit par être lélément médian du tableau. Lorsque cela se produit, il y a (à peu près) n comparaisons effectuées à la couche supérieure de la récursivité, puis (à peu près) n à la couche suivante car il y a deux sous-tableaux de taille n / 2, puis il y a (à peu près) n à la suivante car il y a quatre sous-tableaux de taille n / 4, etc. Puisquil y a des couches Θ (log n) et que chaque couche fait Θ (n) travail, le travail total effectué est Θ (n log n). Dautre part, pensez à choisir le minimum absolu de chaque tableau comme pivot. Ensuite (à peu près) n comparaisons sont effectuées à la couche supérieure, puis (à peu près) n – 1 dans la couche suivante, puis (à peu près) n – 2 dans la suivante, etc. La somme 1 + 2 + 3 + … + n est Θ (n ² ), doù le pire des cas.

Jespère que cela vous aidera!

Commentaires

• Monsieur, quel est le meilleur cas de heapsort nlogn? Si nous considérons que tous les éléments sont identiques, le coût serait simplement ditérer tous les éléments du tableau et de ne pas remonter jusquà la racine. Donc ça devrait être oméga (n) selon moi.
• C’est un bon point. Jassumais des éléments distincts, donc je vais mettre à jour cette réponse.

Puisque personne nest heapSort vraiment adressé pour le moment:

En supposant que vous utilisez un tas max représenté sous forme de tableau et que vous insérez vos éléments max à lenvers dans votre tableau de sortie / à larrière de votre tableau si vous le faites sur place , la pire des entrées pour heapSort est toute entrée qui vous oblige à «faire une bulle» ou à ré-enregistrer chaque fois que vous supprimez un élément. Cela se produit chaque fois que vous essayez de trier un ensemble sans doublons. Ce sera toujours Θ (n log n), comme la dit templatetypedef.

Cette propriété implique que le meilleur cas de heapSort est lorsque tous les éléments sont égaux (Θ (n), puisque vous n’avez pas à vous réorganiser après chaque suppression, ce qui prend un temps de log (n) depuis le la hauteur maximale du tas est log (n)). Cest un peu un cas moche / peu pratique, cependant, cest pourquoi le meilleur cas pour le tri en tas est Θ (n log n).

Commentaires

• Votre point sur le cas peu pratique a été simplement posé dans ma classe dalgorithmes. (méfiez-vous des questions pièges.) Bien sûr, je ‘ suis toujours daccord avec votre point. ( et jai eu ma réponse erronée en conséquence XD)

• Tri rapide

  Pire cas: $ \ mathcal {O} (n ^ 2) $ . Supposons que lélément pivot est toujours lélément le plus à droite: saisissez déjà un liste triée avec des éléments $ n $ . Ainsi, chaque partitionnement mène à une liste avec des éléments $ n-1 $ et une liste avec des éléments $ 0 $ . Même si vous choisissez lélément pivot au hasard , vous pouvez toujours être malchanceux et toujours choisir la valeur maximale dans la liste.

  Soit $ T (n) $ le nombre de comparaisons tri rapide nécessite de trier une liste avec des éléments $ n $ . Pire des cas: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ récursif, $ n $ à la partition)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Meilleur cas: $ \ mathcal {O} (n \ log n) $ . Si lélément pivot est choisi de telle manière quil partitionne la liste uniformément:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 fois $ \ frac {n} { 2} $ récursif, $ n $ vers la partition)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {théorème maître}) \ end {align}

• Tri en tas

  Le pire des cas et la meilleure complexité des cas pour le tri de tas sont tous les deux $ \ mathcal {O} (n \ log n) $ . Par conséquent, le tri de tas nécessite des comparaisons $ \ mathcal {O} (n \ log n) $ pour nimporte quel tableau dentrée. Complexité du tri du tas:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ tas}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ tas}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ text {règle du quotient logarithme}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {align }

Commentaires

• Vous navez ‘ t répondu à toutes les questions de OP ‘, je vais donc répondre à une que vous avez manquée; Le tri de tas nutilise pas ‘ toujours le même nombre de comparaisons pour un nombre donné déléments. Le pire cas est $ a \, n \ log n $ et le meilleur cas est $ b \, n \ log n $, où $ a > b $.
• Notez également que la variante à trois voies a le meilleur cas linéaire pour lentrée dun seul élément.