Complexité spatiale du tri rapide - algorithme, tri, structures de données, tri rapide

J'ai appris que la complexité de l'espace de rapidetrier sans astuce de Sedgewick pour éliminer la récursion de queue est O (n). Mais si nous traçons les appels sur la pile qui sont stockés, c’est O (log n) pas à n’importe quel appel, comme le montre la figure.

Dans la figure,

en calculant la valeur de (1,1), nous stockons les appels de [(1,8), (1,4), (1,2)],

en calculant la valeur de (3,3), nous stockons les appels de [(1,8), (1,4), (3,4)], etc.

qui constituent pour seulement O (log n) l'espace au point de temps. Alors la complexité devient-elle O (n)?

Réponses:

Dans l'exemple d'arbre que vous avez donné ci-dessus, vous avez montrésérie de tri rapide qui sélectionne toujours l’élément médian exact comme point de division à chaque étape. Cela rend la profondeur de récursivité O (log n) et donc, comme vous l'avez indiqué, l'utilisation de l'espace serait O (log n) même sans optimisation.

Mais qu'advient-il si vous obtenez une mauvaise série detri rapide? En d’autres termes, qu’arrivera-t-il si vous choisissez toujours l’élément le plus grand ou le plus petit absolu du tableau comme pivot à chaque point? Ensuite, votre arbre de récurrence ressemblera à ceci:

    size n

size n-1

size n-2

...

1

Maintenant, votre arbre de récursion a la hauteur Θ (n). Par conséquent, s'il est mis en œuvre sans aucun tri final, le tri sélectif utilisera space (n) espace, un par appel récursif actif à chaque point.