Hukommelseskompleksiteten af Quicksort afhænger af, om du overvejer det gennemsnitlige tilfælde, værste tilfælde, eller om du bruger en implementering på stedet. Her er en sammenbrud:
* Gennemsnitlig sag: O (log n)
* I gennemsnit opdeler QuickSort input i omtrent lige store halvdele rekursivt. Dybden af rekursionstræet er omtrent log₂ n.
* Hvert rekursivt opkald kræver lagring af parametrene og returadressen på opkaldsstakken. Derfor er den gennemsnitlige case-rumkompleksitet logaritmisk.
* værste tilfælde: På)
* Det værste tilfælde opstår, når pivotelementet konsekvent resulterer i stærkt ubalancerede partitioner (f.eks. Pivot er altid det mindste eller største element).
*I dette scenarie kan rekursionsdybden blive *n *, hvilket fører til en lineær rumkompleksitet på grund af opkaldsstakken.
* implementering på stedet: O (log n) (gennemsnit) eller o (n) (værst)
* Quicksort kan implementeres på stedet, hvilket betyder, at det kræver minimal yderligere hukommelse * ud over * den originale matrix. Dette gøres ved at bytte elementer inden for input -arrayet direkte i stedet for at skabe mange nye arrays.
* Selv med en implementering på stedet forbruger de rekursive opkald stadig plads på opkaldsstakken. Derfor forbliver rumkompleksiteten O (log n) i gennemsnit og o (n) i værste fald. Nogle implementeringer begrænser rekursionsdybden for at undgå stack-overløbsproblemer i det værste tilfælde ved at skifte til en anden sorteringsalgoritme (som Heapsort), når rekursionen bliver for dyb.
Nøgleovervejelser og optimeringer:
* haleopkaldsoptimering (TCO): Hvis programmeringssprog og kompilator understøtter haleopkaldsoptimering, kan rumkompleksiteten reduceres til O (1) i de bedste og gennemsnitlige tilfælde. TCO implementeres imidlertid ikke almindeligt på mange sprog (f.eks. Python).
* Randomiseret drejepunkt: At vælge pivot hjælper tilfældigt med at undgå det værste tilfælde.
* iterativ implementering: Konvertering af den rekursive Quicksort -algoritme til en iterativ en kan også eliminere rekursionsomkostningen, hvilket reducerer rumkompleksiteten. Dette kan dog være mere kompliceret at implementere.
* hybrid tilgang: Ved at kombinere QuickSort med andre algoritmer, som indsættelsessortering til små underordnede, kan det forbedre ydeevnen og rumforbruget.
Kortfattet:
* Teoretisk set er Quicksorts rumkompleksitet O (log n) i gennemsnit og O (n) i værste tilfælde på grund af den rekursive opkaldsstak.
* I praksis foretrækkes en implementering på stedet normalt at minimere hukommelsesforbruget.
* At forstå potentialet for worst-case adfærd er afgørende, og teknikker som randomiseret drejepunktion kan hjælpe med at afbøde det.
