Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
* Najlepší prípad: O (n log n)
* K tomu dochádza, keď sa otočený zvolený v každom kroku delí pole na zhruba rovnaké polovice. To vedie k vyváženému stromu rekurzie.
* Priemerný prípad: O (n log n)
* V priemere funguje Quicksort veľmi dobre. Výber pivotu nemusí byť pre ňu ideálny, aby dosiahol takmer optimálny výkon.
* Najhorší prípad: O (n^2)
* Stáva sa to, keď je pivot neustále najmenším alebo najväčším prvkom v poli. To vedie k vysoko nevyváženému stromu rekurzie, kde má jeden subproblem veľkosť 0 a druhý má veľkosť N-1. V podstate sa degraduje na výkon podobného výberu alebo triedenia bubliny. Bežným scenárom je, keď je vstupné pole už triedené alebo takmer zoradené.
Dôležité poznámky
* Randomized Quicksort: Variácia Quicksort, ktorá náhodne vyberá čap významne znižuje pravdepodobnosť stretnutia s najhorším scenárom. Randomizovaný Quicksort má priemernú a očakávanú časovú zložitosť O (N log N).
* triedenie na mieste: Quicksort je algoritmus triedenia na mieste (vyžaduje minimálnu ďalšiu pamäť, zvyčajne O (log N) pre zásobník rekurzie).
* Praktický výkon: Napriek možnosti najhoršieho prípadu O (n^2) je Quicksort v praxi často veľmi efektívny a často sa používa v štandardných funkciách triedenia knižníc. Medzi jej výhody patrí jej príroda na mieste a relatívne malé konštantné faktory.
* porovnanie s zlúčením zoradenia: Zlúčenie má vo všetkých prípadoch zaručenú časovú zložitosť O (n log n), ale nie je to na mieste (vyžaduje O (n) pomocný priestor). Preto je Quicksort často uprednostňovaný, keď je priestor hlavným problémom a očakáva sa, že údaje budú primerane dobre distribuované.
v súhrne:
| Prípad | Časová zložitosť
| ----------- | ------------------- |
| Najlepšie | O (n log n) |
| Priemer | O (n log n) |
| Najhoršie | O (n^2) |