|
La complexité de la mémoire de Quicksort dépend si vous envisagez le cas moyen, le pire des cas ou si vous utilisez une implémentation sur place. Voici une répartition :
* Cas moyen : O (log n)
* En moyenne, Quicksort divise l'entrée en moitiés à peu près égales de manière récursive. La profondeur de l'arbre de récursion est d'environ log₂ n.
* Chaque appel récursif nécessite de stocker les paramètres et l'adresse de retour sur la pile d'appels. Par conséquent, la complexité spatiale moyenne est logarithmique.
* Dans le pire des cas : Sur)
* Le pire des cas se produit lorsque l'élément pivot entraîne systématiquement des partitions très déséquilibrées (par exemple, le pivot est toujours l'élément le plus petit ou le plus grand).
* Dans ce scénario, la profondeur de récursion peut devenir *n*, conduisant à une complexité spatiale linéaire due à la pile d'appels.
* Mise en œuvre sur place : O(log n) (moyenne) ou O(n) (pire)
* Le tri rapide peut être implémenté sur place, ce qui signifie qu'il nécessite un minimum de mémoire supplémentaire *au-delà* du tableau d'origine. Cela se fait en échangeant directement les éléments dans le tableau d'entrée, au lieu de créer de nombreux nouveaux tableaux.
* Même avec une implémentation sur place, les appels récursifs consomment toujours de l'espace sur la pile d'appels. Par conséquent, la complexité spatiale reste O(log n) en moyenne et O(n) dans le pire des cas. Certaines implémentations limitent la profondeur de récursion pour éviter les problèmes de débordement de pile dans le pire des cas en passant à un algorithme de tri différent (comme le tri par tas) lorsque la récursion devient trop profonde.
Considérations clés et optimisations :
* Optimisation des appels de queue (TCO) : Si le langage de programmation et le compilateur prennent en charge l'optimisation des appels de fin, la complexité spatiale peut être réduite à O(1) dans les cas meilleurs et moyens. Cependant, le TCO n'est généralement pas implémenté dans de nombreux langages (par exemple Python).
* Sélection pivot aléatoire : Choisir le pivot au hasard permet d’éviter le pire des cas.
* Mise en œuvre itérative : La conversion de l'algorithme récursif Quicksort en un algorithme itératif peut également éliminer la surcharge de récursion, réduisant ainsi la complexité spatiale. Toutefois, cela peut être plus complexe à mettre en œuvre.
* Approche hybride : La combinaison du tri rapide avec d'autres algorithmes, comme le tri par insertion pour les petits sous-réseaux, peut améliorer les performances et l'utilisation de l'espace.
En résumé :
* Théoriquement, la complexité spatiale de Quicksort est de O(log n) en moyenne et de O(n) dans le pire des cas en raison de la pile d'appels récursive.
* En pratique, une implémentation sur place est généralement préférée pour minimiser l'utilisation de la mémoire.
* Comprendre le potentiel du pire comportement est crucial, et des techniques telles que la sélection aléatoire des pivots peuvent aider à l'atténuer.
|
