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

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$\Theta(n^2)$
• Meilleur cas: ; lorsque l'entrée est déjà triée$\Theta(n)$
• Nombre de comparaisons: dans le pire des cas & dans le meilleur des cas$\Theta(n^2)$$\Theta(n)$
• Nombre de swaps: dans le pire / moyen cas & dans le meilleur cas$\Theta(n^2)$$0$

Tri de sélection:

• Cas moyen / pire cas / meilleur cas:$\Theta(n^2)$
• Nombre de comparaisons:$\Theta(n^2)$
• 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.$\Theta(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$\Theta(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ù$\Theta(n+m)$$\Theta(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$\Theta(n^2)$
• Meilleur cas: ; lorsque le pivot divise le tableau en exactement la moitié$\Theta(nlogn)$
• Nombre de comparaisons: dans le pire des cas & dans le meilleur des cas$\Theta(n^2)$$\Theta(nlogn)$
• Nombre d'échanges: dans le pire des cas & dans le meilleur des cas$\Theta(n^2)$$0$

Tri des bulles:

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

Recherche linéaire:

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

Recherche binaire:

• Pire cas / Cas moyen:$\Theta(logn)$
• Meilleur cas: ; lorsque la clé est l'élément central$\Theta(1)$
• Nombre de comparaisons: dans le pire / moyen cas & dans le meilleur cas$\Theta(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

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