Aká je časová zložitosť algoritmu Quicksort?

Časová zložitosť algoritmu Quicksort je nasledovná:

* Najlepší prípad: O (n log n)

* Priemerný prípad: O (n log n)

* Najhorší prípad: O (n^2)

Kde 'n' je počet prvkov v triedení poľa.

Vysvetlenie:

* Najlepšie a priemerné prípady (o (n log n)):

K tomu dochádza, keď čapový prvok neustále rozdeľuje pole na zhruba rovnaké polovice. Hĺbka rekurzie sa stáva logaritmickým (log n) a na každej úrovni rekurzie vykonávame lineárne množstvo práce (n) na rozdelenie poľa. Preto je celková zložitosť O (n log N).

* Najhorší prípad (o (n^2)):

Stáva sa to, keď je čapový prvok neustále najmenším alebo najväčším prvkom v podriadení. V tomto scenári je jedna čiastka prázdna a druhá obsahuje (N-1) prvky. To vedie k vysoko nevyváženej rekurzii, ktorá účinne degraduje algoritmus na výberový druh. Hĺbka rekurzie sa stáva „n“ a na každej úrovni stále vykonávame lineárnu prácu, čo vedie k zložitosti O (n * n) =o (n^2). Bežným scenárom je, keď je vstupné pole už triedené alebo takmer triedené a prvý alebo posledný prvok je vybraný ako otoča.

Zložitosť priestoru:

Vesmírna zložitosť Quicksort závisí od toho, či hovoríte o verzii na mieste alebo nie, a záleží aj na hĺbke rekurzie.

* na mieste Quicksort (s iteratívnou implementáciou na obmedzenie hĺbky rekurzie): O (log n) v priemere v dôsledku zásobníka rekurzie. V najhoršom prípade (aj keď sa dá vyhnúť optimalizácii hovorov alebo explicitnou správou zásobníka), môže to byť O (N). Iteračná implementácia Quicksort používa explicitný zásobník na zabránenie hovorom rekurzie, preto je zložitosť priestoru O (1).

* Non-in-Place Quicksort: O (n) Extra priestor na ukladanie čiastkových podskupín počas rozdelenia.

Kľúčové úvahy:

* Výber piva: Výber pivotu výrazne ovplyvňuje výkon Quicksort. Stratégie, ako je výber náhodného čapu, medián z troch (prvý, stredný, posledný) alebo používanie sofistikovanejších metód, môžu pomôcť vyhnúť sa najhoršiemu scenáru a dosiahnuť v priemere bližšie k výkonu O (N log N).

* na mieste vs. nie na mieste: Na mieste Quicksort upravuje pôvodné pole priamo, čím znižuje potrebu ďalšej pamäte. Verzie, ktoré nie sú na mieste, môžu zjednodušiť logiku rozdelenia, ale vyžadujú ďalší priestor.

* Praktický výkon: Quicksort sa často považuje za jeden z najrýchlejších triediacich algoritmov v praxi (najmä implementácie na mieste), keď sa implementuje dobre, prekonávajú algoritmy, ako je zlúčenie zoradenie v mnohých prípadoch. Je to kvôli jeho relatívne nízkym režijným a dobrým využitiu vyrovnávacej pamäte. Je však nevyhnutné poznať potenciál pre najhorší scenár a používať vhodné techniky výberu otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočných otočov.

Stručne povedané:Zatiaľ čo Quicksort má najhoršiu časovú zložitosť O (n^2), je to všeobecne veľmi účinný algoritmus triedenia s priemernou časovou zložitosťou O (n log N). Kľúčom je zvoliť si dobrý čap, aby sa predišlo najhoršiemu scenáru.

• Predchádzajúca strana: Aká je časová zložitosť vyskočenia prvku z prioritného frontu? 
• Ďalšia strana: Aká je časová zložitosť Quicksort, keď sa prvý prvok vyberie ako pivot?