Complexité des opérations de base des algorithmes de recherche et de tri [clos]

8

Le wiki a une bonne feuille de triche, mais il n'implique pas non. de comparaisons ou de swaps. (bien que le nombre de swaps décide généralement de sa complexité). J'ai donc créé ce qui suit. Les informations suivantes sont-elles correctes? Veuillez me faire savoir s'il y a une erreur, je la corrigerai.

Tri par insertion:

  • Cas moyen / pire cas: ; se produit lorsque l'entrée est déjà triée dans l'ordre décroissantΘ(n2)
  • Meilleur cas: ; lorsque l'entrée est déjà triéeΘ(n)
  • Nombre de comparaisons: dans le pire des cas & dans le meilleur des casΘ(n2)Θ(n)
  • Nombre de swaps: dans le pire / moyen cas & dans le meilleur casΘ(n2)0

Tri de sélection:

  • Cas moyen / pire cas / meilleur cas:Θ(n2)
  • Nombre de comparaisons:Θ(n2)
  • Nombre de swaps: dans le pire des cas / moyenne et dans le meilleur des cas Au plus, l'algorithme nécessite N swaps, une fois que vous permutez un élément en place, vous ne le touchez plus jamais.Θ(n)0

Tri par fusion :

  • Cas moyen / pire cas / meilleur cas: ; n'a pas d'importance du tout si l'entrée est triée ou nonΘ(nlgn)
  • Nombre de comparaisons: dans le pire des cas & dans le meilleur des cas; en supposant que nous fusionnons deux tableaux de taille n et m oùΘ(n+m)Θ(n)n<m
  • Nombre d'échanges: pas d'échanges! [mais nécessite de la mémoire supplémentaire, pas un tri sur place]

Tri rapide:

  • Pire cas: ; arrive l'entrée est déjà triéeΘ(n2)
  • Meilleur cas: ; lorsque le pivot divise le tableau en exactement la moitiéΘ(nlogn)
  • Nombre de comparaisons: dans le pire des cas & dans le meilleur des casΘ(n2)Θ(nlogn)
  • Nombre d'échanges: dans le pire des cas & dans le meilleur des casΘ(n2)0

Tri des bulles:

  • Pire cas:Θ(n2)
  • Meilleur cas: ; sur déjà triéΘ(n)
  • Nombre de comparaisons: dans le pire des cas et le meilleur des casΘ(n2)
  • Nombre d'échanges: dans le pire des cas & dans le meilleur des casΘ(n2)0

Recherche linéaire:

  • Pire cas: ; clé de recherche absente ou dernier élémentΘ(n)
  • Meilleur cas: ; premier élémentΘ(1)
  • Nombre de comparaisons: dans le pire des cas & dans le meilleur des casΘ(n)1

Recherche binaire:

  • Pire cas / Cas moyen:Θ(logn)
  • Meilleur cas: ; lorsque la clé est l'élément centralΘ(1)
  • Nombre de comparaisons: dans le pire / moyen cas & dans le meilleur casΘ(logn)1

  1. Je n'ai considéré que les algorithmes de recherche et de tri de base.
  2. On suppose ci-dessus que les algorithmes de tri produisent une sortie dans l'ordre croissant
  3. Sources: Le génial CLRS et ce Wiki
avi
la source
Pour discuter des mérites de cette (sorte de) question, veuillez vous joindre à nous dans le chat .
Raphael
1
Ce n'est pas une question, c'est donc hors sujet.
David Richerby
J'ai voté pour fermer aussi. C'est peut-être aussi difficile à récupérer parce que la "question" est assez large (quels sont les algorithmes de recherche et de tri de base, exactement?)
Juho

Réponses:

-2

Pour l'algorithme général de tri à bulles, les comparaisons les plus défavorables sont Mais pour l'algorithme de cas spécial où vous ajoutez un indicateur pour indiquer qu'il y a eu un échange lors de la passe précédente. S'il n'y avait pas de swaps, nous sortons de la boucle car le tableau est déjà trié. Dans ce cas, les comparaisons sont non 0.Θ(n2)n

Pour le tri rapide, vous avez mentionné que les swaps les plus défavorables sont . Dans le pire des cas, le tri rapide est lorsque tous les éléments sont triés, il n'y aura donc pas de swaps, il devrait donc être nul.n2

Nikhil Mahajan
la source
1
Je ne comprends pas ta réponse. Détecter "aucun échange" dans le tri à bulles le rend certainement plus rapide mais, si l'entrée est dans l'ordre opposé à la sortie, vous avez toujours besoinΘ(n2)swaps, même avec la détection "no swap". Quicksort fonctionne normalement dans le tempsO(nlogn) donc le meilleur cas ne peut pas être n2swaps.
David Richerby
Merci d'avoir édité mon commentaire, je suis nouveau sur SE. Eh bien, j'aurais dû être plus clair à ce sujet. je viens de modifier mon commentaire ci-dessus. J'essayais de dire que les meilleures comparaisons de cas ne peuvent pas être 0 en cas de tri Bubble, il doit être n. lorsque le tableau est trié et que vous utilisez l'indicateur pour indiquer l'échange lors de la passe précédente. s'il n'y a pas d'échange dans la passe précédente, le tableau est déjà trié, donc pas besoin de courir plus loin pour la première passe, nous faisons n comparaisons. Pour le tri rapide, je parle de comparaisons et d'échanges et non de complexité temporelle, dans le pire des cas, tous les éléments sont triés, donc aucun échange n'est nécessaire.
Nikhil Mahajan
Dans le cas normal, le tri rapide s'exécute dans le temps O(nlogn). Par conséquent, le meilleur cas est égalementO(nlogn) pas de temps (cela pourrait être plus rapide mais O()ne donne qu'une limite supérieure). DansO(nlogn) étapes, vous ne pouvez rien faire n2fois - comparaisons, swaps ou autre chose. Vous ne pouvez pas utiliser plus deO(nlogn)mémoire non plus. Le meilleur cas pour toute mesure de complexité ne peut pas être supérieur àO(nlogn).
David Richerby
Vous avez raison, j'ai modifié ma réponse pour le tri rapide.
Nikhil Mahajan