Rumkompleksiteten af QuickSort-algoritmen afhænger af den specifikke implementering, og om det er gjort på stedet. Der er to hovedscenarier at overveje:
1. Gennemsnitlig og bedste sag:
* Rumkompleksitet:O (log n)
* Dette opnås, når QuickSort implementeres med følgende optimeringer:
* placering på stedet: Quicksort sigter typisk på at omarrangere elementerne direkte inden for den originale array, hvilket minimerer behovet for ekstra plads til at gemme mellemliggende partitioner.
* hale-call optimering (eller iteration): For at håndtere de rekursive opkald behandles den mindre partition altid *rekursivt *, mens den større partition behandles *iterativt *(f.eks. Brug af en løkke i stedet for et andet rekursivt opkald). Dette hjælper med at begrænse den maksimale dybde af rekursionen.
* Rumkompleksiteten stammer primært fra opkaldsstakken, der bruges til at styre de rekursive opkald. I de bedste og gennemsnitlige tilfælde er rekursionsdybden logaritmisk (O (log n)), hvilket betyder, at det maksimale antal funktionsopkald, der venter på stakken, er proportional med log n. Hvert opkald kræver en lille konstant plads.
2. Værste tilfælde:
* rumkompleksitet:O (n)
* Det værste tilfælde opstår, når pivotelementet konsekvent vælges dårligt, såsom altid at vælge det mindste eller største element. Dette fører til meget ubalancerede partitioner. Som et resultat indeholder den ene partition kun pivot, og den anden indeholder alle de resterende `n-1` elementer.
* I denne situation bliver rekursionsdybden lineær (O (n)). Opkaldsstakken vokser til en dybde på `n`, hvilket resulterer i en rumkompleksitet af O (n).
Sammendrag:
| Sag | Rumkompleksitet |
| ------------ | -------------------- |
| Bedste | O (log n) |
| Gennemsnit | O (log n) |
| Værste | O (n) |
Vigtige overvejelser:
* sted: Quicksort betragtes generelt som en sorteringsalgoritme på stedet, fordi den udfører de fleste af sine operationer direkte inden for det originale array. Imidlertid bidrager opkaldsstakken, der er nødvendig til rekursion, til rumkompleksiteten.
* Valg af drejning: Strategier til forbedring af driftsvalg, såsom at vælge en tilfældig pivot eller median-of-tre-drejebilledet, kan hjælpe med at reducere sandsynligheden for det værste tilfælde.
* ikke-rekursive (iterative) Quicksort: Det er muligt at implementere QuickSort helt iterativt ved hjælp af en stakdatakonstruktion til at administrere partitionerne. Dette kan give mere kontrol over rumforbruget og potentielt forbedre ydelsen, især når rekursionsdybde er et problem. Rumkompleksiteten afhænger derefter af den maksimale størrelse på den krævede stak, som stadig kan være O (n) i værste tilfælde, men er mere tilbøjelig til at være O (log n) med passende partitioneringsstrategier.
Eksempel:
Lad os sige, at du har en række 1000 elementer.
* Gennemsnitlig/bedste sag: Den maksimale rekursionsdybde vil sandsynligvis være omkring log₂ (1000) ≈ 10. Så den plads, der er nødvendig til opkaldsstakken, ville være proportional med 10.
* værste tilfælde: Rekursionsdybden kan være 1000, og den plads, der er nødvendig til opkaldsstakken, ville være proportional med 1000.
Afslutningsvis, selvom QuickSort ofte beskrives som at have O (log n) rumkompleksitet, er det vigtigt at huske, at dette er det gennemsnitlige tilfælde med optimeringer som opdeling på stedet og optimering af halekald. Den værste case-rumkompleksitet er O (n), som kan være betydelig for store datasæt, hvis implementeringen ikke er omhyggelig.
