Aká je priestorová zložitosť algoritmu Quicksort?

Vesmírna zložitosť algoritmu Quicksort závisí od konkrétnej implementácie a od toho, či sa to robí na mieste. Existujú dva hlavné scenáre, ktoré je potrebné zvážiť:

1. Priemerný a najlepší prípad:

* Zložitosť priestoru:o (log n)

* Dosahuje sa to, keď je spoločnosť Quicksort implementovaná s nasledujúcimi optimalizáciami:

* na mieste rozdelenie: Quicksort sa zvyčajne zameriava na usporiadanie prvkov priamo v pôvodnom poli, čím sa minimalizuje potreba ďalšieho priestoru na ukladanie stredných oddielov.

* Optimalizácia koncového volania (alebo iterácia): Na zvládnutie rekurzívnych hovorov sa menší oddiel vždy spracováva *rekurzívne *, zatiaľ čo väčší oddiel sa spracováva *iteratívne *(napr. Používanie slučky namiesto iného rekurzívneho hovoru). To pomáha obmedziť maximálnu hĺbku rekurzie.

* Zložitosť priestoru vzniká predovšetkým zo zásobníka hovorov, ktorý sa používa na správu rekurzívnych hovorov. V najlepších a priemerných prípadoch je hĺbka rekurzie logaritmická (o (log n)), čo znamená, že maximálny počet funkčných hovorov čakajúcich na zásobníku je úmerný log n. Každý hovor vyžaduje malé konštantné množstvo miesta.

2. Najhorší prípad:

* Zložitosť priestoru:o (n)

* Najhorší scenár sa vyskytuje, keď sa čapový prvok neustále vyberá zle, napríklad vždy výber najmenšieho alebo najväčšieho prvku. To vedie k vysoko nevyváženým oddielom. Výsledkom je, že jedna oddiel obsahuje iba pivot a druhý obsahuje všetky zostávajúce prvky `N-1`.

* V tejto situácii sa hĺbka rekurzie stáva lineárnou (o (n)). Stack call rastie do hĺbky `n`, čo vedie k zložitosti priestoru O (n).

Zhrnutie:

| Prípad | Zložitosť priestoru

| ------------ | ---------------------- |

| Najlepšie | O (log n) |

| Priemer | O (log n) |

| Najhoršie | O (n) |

Dôležité úvahy:

* na mieste: Quicksort sa všeobecne považuje za algoritmus triedenia na mieste, pretože vykonáva väčšinu svojich operácií priamo v pôvodnom poli. Stack volania potrebný na rekurziu však prispieva k zložitosti vesmíru.

* Výber piva: Stratégie na zlepšenie výberu pivotu, ako napríklad výber náhodného čapu alebo mediánového triku, môžu pomôcť znížiť pravdepodobnosť najhoršieho scenára.

* ne-rekurzívne (iteratívne) Quicksort: Je možné implementovať QuickSort úplne iteratívne pomocou štruktúry dát zásobníka na správu oddielov. To môže poskytnúť väčšiu kontrolu nad využitím priestoru a potenciálne zlepšiť výkon, najmä ak je problémom hĺbka rekurzie. Zložitosť priestoru by potom závisela od maximálnej veľkosti požadovaného zásobníka, ktorý môže byť v najhoršom prípade stále O (n), ale je pravdepodobnejšie, že bude O (log N) s príslušnými stratégiami rozdelenia.

Príklad:

Povedzme, že máte celý rad 1 000 prvkov.

* priemer/najlepší prípad: Maximálna hĺbka rekurzie bude pravdepodobne okolo log₂ (1000) ≈ 10. Takže priestor potrebný pre zásobník hovorov by bol úmerný 10.

* Najhorší prípad: Hĺbka rekurzie by mohla byť 1000 a priestor potrebný pre zásobník hovorov by bol úmerný 1000.

Záverom je, že zatiaľ čo Quicksort je často opísaný ako zložitosť priestoru O (log N), je nevyhnutné pamätať na to, že ide o priemerný prípad optimalizácií, ako je rozdelenie na mieste a optimalizácia chvosta. Najhoršia zložitosť priestoru je O (n), ktorá môže byť významná pre veľké súbory údajov, ak implementácia nie je opatrná.

• Predchádzajúca strana: Aká je zložitosť pamäte algoritmu Quicksort? 
• Ďalšia strana: Aká je časová zložitosť algoritmu Quicksort z hľadiska veľkej notácie?