Aká je časová zložitosť algoritmu Quicksort z hľadiska veľkej notácie?

Časová zložitosť Quicksort, vyjadrená vo veľkej notácii, sa líši v závislosti od vstupných údajov:

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

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

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

Tu je porucha:

* Najlepší a priemerný prípad (o (n log n)): K tomu dochádza, keď sa otočný prvok zvolený v každom kroku delí pole na zhruba rovnaké polovice. V tomto scenári algoritmus robí log n rekurzívne hovory (pretože účinne na polovicu veľkosti problému) a každá úroveň rekurzie vyžaduje prácu O (N) na rozdelenie poľa. Preto je celková časová zložitosť O (n log n).

* Najhorší prípad (o (n^2)): Stáva sa to, keď je čapový prvok opakovane najmenším alebo najväčším prvkom v poli. To vedie k veľmi nerovnomerným oddielom. V podstate namiesto rozdelenia poľa na polovicu znižujete veľkosť problému iba zakaždým iba o jeden prvok. To má za následok rekurzívne hovory a každé volanie stále trvá O (n) čas na oddiel (pretože porovnávate takmer všetky prvky). V dôsledku toho sa celková časová zložitosť znižuje na O (n^2).

Zmiernenie najhoršieho scenára:

Najhorší scenár možno zmierniť:

* Randomizovaný výber pivotu: Výber čapu náhodne pomáha vyhnúť sa neustálemu výberu najmenšieho alebo najväčšieho prvku, vďaka čomu je prípad O (n^2) oveľa menej pravdepodobný.

* Medián z troch výberov pivotov: Výber mediánu prvého, stredného a posledného prvkov poľa, pretože Pivot môže tiež pomôcť vyhnúť sa dôsledne zlým výberom čapu.

V praxi je Quicksort často veľmi efektívny kvôli svojmu dobrému výkonu priemerného prípadu a skutočnosti, že má tendenciu mať nižšie konštantné faktory ako iné algoritmy triedenia O (n log N), ako je zlúčenie. Je však dôležité poznať potenciál pre O (n^2) najhoršie správanie.

• Predchádzajúca strana: Aká je priestorová zložitosť algoritmu Quicksort? 
• Ďalšia strana: Aká je časová zložitosť vyskočenia prvku z prioritného frontu?