|
La complexité spatiale de l'algorithme Quicksort dépend de l'implémentation spécifique et du fait qu'elle soit effectuée sur place. Il y a deux scénarios principaux à considérer :
1. Moyenne et meilleur cas :
* Complexité spatiale :O(log n)
* Ceci est obtenu lorsque Quicksort est implémenté avec les optimisations suivantes :
* Partitionnement sur place : Le tri rapide vise généralement à réorganiser les éléments directement dans le tableau d'origine, minimisant ainsi le besoin d'espace supplémentaire pour stocker les partitions intermédiaires.
* Optimisation des appels de queue (ou itération) : Pour gérer les appels récursifs, la plus petite partition est toujours traitée *récursivement*, tandis que la plus grande partition est traitée *itérativement* (par exemple, en utilisant une boucle au lieu d'un autre appel récursif). Cela permet de limiter la profondeur maximale de la récursion.
* La complexité spatiale provient principalement de la pile d'appels utilisée pour gérer les appels récursifs. Dans le meilleur et dans la moyenne des cas, la profondeur de récursion est logarithmique (O(log n)), ce qui signifie que le nombre maximum d'appels de fonction en attente sur la pile est proportionnel au log n. Chaque appel nécessite une petite quantité constante d’espace.
2. Dans le pire des cas :
* Complexité spatiale :O(n)
* Le pire des cas se produit lorsque l'élément pivot est systématiquement mal choisi, par exemple en sélectionnant toujours l'élément le plus petit ou le plus grand. Cela conduit à des partitions très déséquilibrées. En conséquence, une partition contient uniquement le pivot et l'autre contient tous les éléments « n-1 » restants.
* Dans cette situation, la profondeur de récursion devient linéaire (O(n)). La pile d'appels atteint une profondeur de « n », ce qui entraîne une complexité spatiale de O(n).
Résumé :
| Cas | Complexité spatiale |
|------------|----------|
| Meilleur | O(logn) |
| Moyenne | O(logn) |
| Le pire | O(n) |
Considérations importantes :
* Sur place : Le tri rapide est généralement considéré comme un algorithme de tri sur place car il effectue la plupart de ses opérations directement dans le tableau d'origine. Cependant, la pile d'appels nécessaire à la récursivité contribue à la complexité de l'espace.
* Sélection pivot : Les stratégies visant à améliorer la sélection des pivots, telles que le choix d’un pivot aléatoire ou du pivot médian sur trois, peuvent contribuer à réduire la probabilité du pire des cas.
* Tri rapide non récursif (itératif) : Il est possible d'implémenter Quicksort de manière entièrement itérative en utilisant une structure de données en pile pour gérer les partitions. Cela peut fournir plus de contrôle sur l’utilisation de l’espace et potentiellement améliorer les performances, en particulier lorsque la profondeur de récursion est un problème. La complexité spatiale dépendrait alors de la taille maximale de la pile requise, qui peut toujours être O(n) dans le pire des cas mais est plus susceptible d'être O(log n) avec des stratégies de partitionnement appropriées.
Exemple :
Disons que vous disposez d'un tableau de 1 000 éléments.
* Moyenne/Meilleur cas : La profondeur de récursion maximale est probablement d'environ log₂(1000) ≈ 10. Ainsi, l'espace nécessaire pour la pile d'appels serait proportionnel à 10.
* Dans le pire des cas : La profondeur de récursion pourrait être de 1 000 et l'espace nécessaire pour la pile d'appels serait proportionnel à 1 000.
En conclusion, même si le tri rapide est souvent décrit comme ayant une complexité spatiale O(log n), il est crucial de se rappeler qu'il s'agit du cas moyen avec des optimisations telles que le partitionnement sur place et l'optimisation des appels finals. La complexité spatiale dans le pire des cas est O(n), ce qui peut être important pour les grands ensembles de données si la mise en œuvre n'est pas prudente.
|
