|
La complexité temporelle de l'algorithme Quicksort est la suivante :
* Meilleur cas : O (n journal n)
* Cas moyen : O (n journal n)
* Dans le pire des cas : O(n^2)
Où « n » est le nombre d'éléments du tableau en cours de tri.
Explication :
* Meilleur cas et cas moyen (O(n log n)) :
Cela se produit lorsque l'élément pivot divise systématiquement le tableau en moitiés à peu près égales. La profondeur de récursion devient logarithmique (log n), et à chaque niveau de récursion, nous effectuons une quantité linéaire de travail (n) pour partitionner le tableau. Par conséquent, la complexité globale est O(n log n).
* Pire des cas (O(n^2)) :
Cela se produit lorsque l’élément pivot est systématiquement l’élément le plus petit ou le plus grand du sous-tableau. Dans ce scénario, un sous-tableau est vide et l'autre contient (n-1) éléments. Cela conduit à une récursion très déséquilibrée, dégradant effectivement l’algorithme vers un tri par sélection. La profondeur de récursion devient « n », et à chaque niveau, nous effectuons toujours un travail linéaire, ce qui donne une complexité O(n * n) =O(n^2). Un scénario courant est celui où le tableau d'entrée est déjà trié ou presque trié et que le premier ou le dernier élément est choisi comme pivot.
Complexité spatiale :
La complexité spatiale de Quicksort dépend du fait que vous parlez ou non de la version sur place, et elle dépend également de la profondeur de récursion.
* Tri rapide sur place (avec implémentation itérative pour limiter la profondeur de récursion) : O (log n) en moyenne en raison de la pile de récursivité. Dans le pire des cas (bien qu'évitable avec l'optimisation des appels de fin ou la gestion explicite de la pile), cela peut être O(n). Une implémentation itérative du tri rapide utilise une pile explicite pour éviter les appels récursifs, la complexité spatiale est donc O(1).
* Tri rapide non sur place : O(n) espace supplémentaire pour stocker les sous-tableaux pendant le partitionnement.
Considérations clés :
* Sélection pivot : Le choix du pivot affecte considérablement les performances de Quicksort. Des stratégies telles que le choix d'un pivot aléatoire, la médiane sur trois (premier, milieu, dernier) ou l'utilisation de méthodes plus sophistiquées peuvent aider à éviter le pire des cas et à obtenir des performances plus proches de O(n log n) en moyenne.
* Sur place ou non : Le tri rapide sur place modifie directement le tableau d'origine, réduisant ainsi le besoin de mémoire supplémentaire. Les versions non sur place peuvent simplifier la logique de partitionnement mais nécessitent un espace supplémentaire.
* Performances pratiques : Le tri rapide est souvent considéré comme l'un des algorithmes de tri les plus rapides en pratique (en particulier les implémentations sur place) lorsqu'il est bien implémenté, surpassant les algorithmes comme Merge Sort dans de nombreux cas. Cela est dû à sa surcharge relativement faible et à sa bonne utilisation du cache. Cependant, il est crucial d’être conscient du potentiel du pire des cas et d’utiliser des techniques de sélection pivot appropriées.
En résumé :bien que Quicksort ait une complexité temporelle dans le pire des cas de O(n^2), il s'agit généralement d'un algorithme de tri très efficace avec une complexité temporelle moyenne de O(n log n). La clé est de choisir un bon pivot pour éviter le pire des cas.
|
