Aká je časová zložitosť Quicksort, keď sa prvý prvok vyberie ako pivot?

Časová zložitosť Quicksort, keď je prvý prvok vybraný ako Pivot je:

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

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

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

Vysvetlenie:

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

K tomu dôjde, keď je vstupné pole už triedené (buď vo vzostupnom alebo zostupnom poradí) alebo takmer zoradené. Keď je pole triedené, pivot bude vždy najmenším (alebo najväčším) prvkom. Výsledkom je vysoko nevyvážené oddiely.

Napríklad, ak je pole zoradené do vzostupného poradia a prvým prvkom je vždy čap:

1. Prvý prvok je vybraný ako čap.

2. Všetky ostatné prvky sú väčšie ako Pivot, takže všetci skončia v správnom oddiele.

3. Ľavý oddiel je prázdny.

4. Rekurzívny hovor sa potom uskutoční na podskupine veľkosti `n-1`.

Tento proces sa opakuje, čo vedie k hĺbke rekurzie `n`. Na každej úrovni `I 'rekurzie vykonávame` n - porovnania. Celkový počet porovnaní sa stáva zhruba `n + (n-1) + (n-2) + ... + 1`, čo sa rovná` n (n + 1)/2`, čo je o (n^2).

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

Najlepší scenár nastane, keď pivot neustále rozdeľuje pole na dve rovnaké (alebo takmer rovnaké) polovice. V tejto situácii sa hĺbka rekurzie stáva `log n` a na každej úrovni vykonávame porovnania` n`, čo vedie k časovej zložitosti `o (n log n)`.

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

V priemere funguje Quicksort veľmi dobre. Keď výber čapu neustále vytvára primerane vyvážené oddiely, časová zložitosť je `o (n log n)`. „Priemerný“ predpokladá, že vstup je náhodne usporiadaný a výber čap nie je dôsledne zlý.

Vplyv výberu pivotu:

Výber spoločnosti Pivot výrazne ovplyvňuje výkon Quicksort. Výber prvého prvku ako Pivot je naivná stratégia a môže viesť k najhoršiemu scenáru v mnohých bežných situáciách.

Techniky zmierňovania:

Aby sa predišlo najhoršiemu scenáru pri používaní Quicksort, je nevyhnutné zvoliť si dobrý otoč. Tu je niekoľko bežných techník:

* Random Pivot: Výber náhodného prvku ako pivotu je jednoduchý a efektívny spôsob, ako sa vyhnúť najhoršiemu scenáru. Vďaka tomu je výkon algoritmu menej závislý od počiatočného poradia vstupu.

* medián z troch: Vyberte si medián prvého, stredného a posledného prvkov poľa ako Pivot. Toto často poskytuje lepší čap ako jednoducho výber prvého prvku.

* Ďalšie stratégie výberu pivotu: Existujú sofistikovanejšie stratégie výberu čapov, ale často pridávajú režijné náklady, ktoré prevažujú nad ich výhodami v prípade typických prípadov použitia.

v súhrne:

Použitie prvého prvku ako Pivot v Quicksort môže byť zlá stratégia, najmä ak bude vstupné pole pravdepodobne triedené alebo takmer zoradené. Najlepšie je použiť stratégie výberu pivotov, ktoré sa snažia vytvoriť vyváženejšie oddiely, aby sa zabezpečilo, že algoritmus funguje bližšie k jeho priemernému prípadu `o (n log n)„ časovej zložitosti.

• Predchádzajúca strana: Aká je časová zložitosť algoritmu Quicksort? 
• Ďalšia strana: Aká je najhoršia časová zložitosť Quicksort?