Tidskomplexiteten för Quicksort, uttryckt i stor O -notation, varierar beroende på inmatningsdata:
* bästa fall: O (n log n)
* Genomsnittligt fall: O (n log n)
* värsta fall: O (n^2)
Här är en uppdelning:
* Bästa fall och genomsnittligt fall (O (n log n)): Detta inträffar när pivotelementet som valts vid varje steg delar upp matrisen i ungefär lika stora halvor. I det här scenariot gör algoritmen log n rekursiva samtal (eftersom det effektivt halverar problemstorleken), och varje rekursionsnivå kräver o (n) arbete för att dela upp matrisen. Därför är den övergripande tidskomplexiteten O (n log n).
* värsta fall (o (n^2)): Detta händer när pivotelementet upprepade gånger är det minsta eller största elementet i matrisen. Detta leder till mycket ojämna partitioner. I huvudsak, istället för att dela upp matrisen i hälften, minskar du bara problemstorleken med ett element varje gång. Detta resulterar i n rekursiva samtal, och varje samtal tar fortfarande o (n) tid att partitionera (eftersom du jämför nästan alla element). Följaktligen försämras den totala tidskomplexiteten till O (n^2).
Mitigering av värsta fall:
Det värsta fallet kan mildras av:
* Randomiserat val av pivot: Att välja pivot hjälper slumpmässigt att undvika att konsekvent välja det minsta eller största elementet, vilket gör o (n^2) fallet mycket mindre troligt.
* Median-of-Three Pivot Selection: Att välja medianen för de första, mitten och sista elementen i matrisen eftersom pivoten också kan hjälpa till att undvika konsekvent dåliga pivotval.
I praktiken är QuickSort ofta mycket effektiv på grund av dess goda medelhögprestanda och det faktum att det tenderar att ha lägre konstant faktorer än andra O (N Log N) sorteringsalgoritmer som Merge Sort. Det är emellertid viktigt att vara medveten om potentialen för O (n^2) värsta fall.
