Tidskomplexiteten för Quicksort när det första elementet väljs som pivot är:
* Värsta fall:o (n^2)
* bästa fall:o (n log n)
* Medelfall:o (n log n)
Förklaring:
* Värsta fall:o (n^2)
Detta inträffar när ingångsuppsättningen redan är sorterad (antingen i stigande eller fallande ordning) eller nästan sorteras. När matrisen sorteras kommer pivoten alltid att vara det minsta (eller största) elementet. Detta resulterar i mycket obalanserade partitioner.
Till exempel, om matrisen är sorterad i stigande ordning och det första elementet alltid är pivot:
1. Det första elementet väljs som pivot.
2. Alla andra element är större än pivoten, så de hamnar alla i rätt partition.
3. Den vänstra partitionen är tom.
4. Det rekursiva samtalet görs sedan på en underlag av storleken `n-1`.
Denna process upprepas, vilket leder till ett rekursionsdjup på `n '. På varje nivå "i" i rekursionen utför vi "n - i" jämförelser. Det totala antalet jämförelser blir ungefär `n + (n-1) + (n-2) + ... + 1`, vilket är lika med` n (n + 1)/2`, vilket är o (n^2).
* bästa fall:o (n log n)
Det bästa fallet händer när pivoten konsekvent delar upp matrisen i två lika (eller nästan lika) halvor. I denna situation blir rekursionsdjupet `log n ', och på varje nivå utför vi` n` jämförelser, vilket resulterar i en tidskomplexitet av `o (n log n)'.
* Medelfall:o (n log n)
I genomsnitt presterar QuickSort mycket bra. När pivotvalet konsekvent producerar rimligt balanserade partitioner är tidskomplexiteten `o (n log n)`. Det "genomsnittliga" antar att ingången slumpmässigt beställs och pivotvalet inte är konsekvent dåligt.
Effekten av Pivot Choice:
Valet av pivot påverkar avsevärt prestanda för Quicksort. Att välja det första elementet som pivot är en naiv strategi och kan leda till värsta fall i många vanliga situationer.
Mitigationstekniker:
För att undvika det värsta fallet när du använder Quicksort är det avgörande att välja en bra pivot. Här är några vanliga tekniker:
* Random Pivot: Att välja ett slumpmässigt element som pivot är ett enkelt och effektivt sätt att undvika det värsta fallet. Detta gör algoritmens prestanda mindre beroende av den första beställningen av ingången.
* median--of-tre: Välj medianen för den första, mitten och sista elementen i matrisen som pivot. Detta ger ofta en bättre pivot än att bara välja det första elementet.
* Andra strategier för val av pivot: Det finns mer sofistikerade strategier för pivotval, men de lägger ofta över huvudet som uppväger deras fördelar för typiska användningsfall.
Sammanfattningsvis:
Att använda det första elementet som pivot i Quicksort kan vara en dålig strategi, särskilt om ingångsuppsättningen troligen kommer att sorteras eller nästan sorteras. Det är bäst att använda pivotvalsstrategier som försöker producera mer balanserade partitioner för att säkerställa att algoritmen fungerar närmare dess genomsnittliga fall `o (n log n)` tidskomplexitet.
